首页 > 代码库 > LA 2218 (半平面交) Triathlon
LA 2218 (半平面交) Triathlon
题意：
有n个选手，铁人三项有连续的三段，对于每段场地选手i分别以vi, ui 和 wi匀速通过。
对于每个选手，问能否通过调整每种赛道的长度使得他成为冠军(不能并列)。
分析：
粗一看，这不像一道计算几何的题目。
假设赛道总长度是1，第一段长x，第二段长y，第三段则是1-x-y
那么可以计算出每个选手完成比赛的时间Ti
对于选手i，若要成为冠军则有Ti < Tj (i ≠ j)
于是就有n-1个不等式，每个不等式都代表一个半平面。
在加上x>0, y>0, 1-x-y>0 这三个半平面一共有n+2个半平面。如果这些半平面交非空，则选手i可以成为冠军。
最终，还是转化成了半平面交的问题。
细节：
- 对于半平面 ax+by+c > 0 所对应的向量(b, -a)是和系数的正负没有关系的，可以自己试验下。开始我纠结了好长时间
if(fabs(a) > fabs(b)) P = Point(-c/a, 0)else P = Point(0, -c/b);
对于这段代码不是太清楚它的含义，因为不管怎样P都是在ax+by+c = 0 这条直线上的。我猜可能是减小浮点运算的误差吧？
1 //#define LOCAL 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <vector> 7 using namespace std; 8 9 const double eps = 1e-6; 10 const int maxn = 100 + 10; 11 int v[maxn], u[maxn], w[maxn]; 12 13 struct Point 14 { 15 double x, y; 16 Point(double x=0, double y=0):x(x), y(y) {} 17 }; 18 typedef Point Vector; 19 Point operator + (Point a, Point b) { return Point(a.x+b.x, a.y+b.y); } 20 Point operator - (Point a, Point b) { return Point(a.x-b.x, a.y-b.y); } 21 Vector operator * (Vector a, double p) { return Vector(a.x*p, a.y*p); } 22 Vector operator / (Vector a, double p) { return Vector(a.x/p, a.y/p); } 23 bool operator < (const Point& a, const Point& b) 24 { return a.x < b.x || (a.x == b.x && a.y < b.y); } 25 bool operator == (const Point& a, const Point& b) 26 { return a.x == b.x && a.y == b.y; } 27 double Dot(const Vector& a, const Vector& b) { return a.x*b.x + a.y*b.y; } 28 double Cross(const Vector& a, const Vector& b) { return a.x*b.y - a.y*b.x; } 29 double Length(const Vector& a) { return sqrt(Dot(a, a)); } 30 Vector Normal(const Vector& a) 31 { 32 double l = Length(a); 33 return Vector(-a.y/l, a.x); 34 } 35 36 double PolygonArea(const vector<Point>& p) 37 { 38 int n = p.size(); 39 double ans = 0.0; 40 for(int i = 1; i < n-1; ++i) 41 ans += Cross(p[i]-p[0], p[i+1]-p[0]); 42 return ans/2; 43 } 44 45 struct Line 46 { 47 Point P; 48 Vector v; 49 double ang; 50 Line() {} 51 Line(Point p, Vector v):P(p), v(v) { ang = atan2(v.y, v.x); } 52 bool operator < (const Line& L) const 53 { 54 return ang < L.ang; 55 } 56 }; 57 58 bool OnLeft(const Line& L, Point p) 59 { 60 return Cross(L.v, p-L.P) > 0; 61 } 62 63 Point GetLineIntersevtion(const Line& a, const Line& b) 64 { 65 Vector u = a.P - b.P; 66 double t = Cross(b.v, u) / Cross(a.v, b.v); 67 return a.P + a.v*t; 68 } 69 70 vector<Point> HalfplaneIntersection(vector<Line> L) 71 { 72 int n = L.size(); 73 sort(L.begin(), L.end()); 74 75 int first, last; 76 vector<Point> p(n); 77 vector<Line> q(n); 78 vector<Point> ans; 79 80 q[first=last=0] = L[0]; 81 for(int i = 1; i < n; ++i) 82 { 83 while(first < last && !OnLeft(L[i], p[last-1])) last--; 84 while(first < last && !OnLeft(L[i], p[first])) first++; 85 q[++last] = L[i]; 86 if(fabs(Cross(q[last].v, q[last-1].v)) < eps) 87 { 88 last--; 89 if(OnLeft(q[last], L[i].P)) q[last] = L[i]; 90 } 91 if(first < last) p[last-1] = GetLineIntersevtion(q[last-1], q[last]); 92 } 93 while(first < last && !OnLeft(q[first], p[last-1])) last--; 94 if(last - first <= 1) return ans; 95 p[last] = GetLineIntersevtion(q[first], q[last]); 96 97 for(int i = first; i <= last; ++i) ans.push_back(p[i]); 98 return ans; 99 }100 101 int main(void)102 {103 #ifdef LOCAL104 freopen("2218in.txt", "r", stdin);105 #endif106 107 int n;108 while(scanf("%d", &n) == 1 && n)109 {110 for(int i = 0; i < n; ++i) scanf("%d%d%d", &v[i], &u[i], &w[i]);111 for(int i = 0; i < n; ++i)112 {113 int ok = 1;114 double k = 10000;115 vector<Line> L;116 for(int j = 0; j < n; ++j) if(j != i)117 {118 if(v[i]<=v[j] && u[i]<=u[j] && w[i]<=w[j]) { ok = 0; break; }119 if(v[i]>v[j] && u[i]>u[j] && w[i]>w[j]) continue;120 121 double a = (k/v[j]-k/v[i]+k/w[i]-k/w[j]);122 double b = (k/u[j]-k/u[i]+k/w[i]-k/w[j]);123 double c = k/w[j]-k/w[i];124 //L.push_back(Line(Point(0, -c/b), Vector(b, -a)));125 Point P;126 Vector V(b, -a);127 if(fabs(a) > fabs(b)) P = Point(-c/a, 0);128 else P = Point(0, -c/b);129 L.push_back(Line(P, V));130 }131 if(ok)132 {133 L.push_back(Line(Point(0, 0), Vector(0, -1)));134 L.push_back(Line(Point(0, 0), Vector(1, 0)));135 L.push_back(Line(Point(0, 1), Vector(-1, 1)));136 vector<Point> Poly = HalfplaneIntersection(L);137 if(Poly.empty()) ok = 0;138 }139 if(ok) puts("Yes"); else puts("No");140 }141 }142 143 return 0;144 }
LA 2218 (半平面交) Triathlon
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。