题意：
有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, )
else P = Point(, -c/b);对于这段代码不是太清楚它的含义，因为不管怎样P都是在ax+by+c = 0 这条直线上的。我猜可能是减小浮点运算的误差吧？
//#define LOCAL
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std; const double eps = 1e-;
const int maxn = + ;
int v[maxn], u[maxn], w[maxn]; struct Point
{
double x, y;
Point(double x=, double y=):x(x), y(y) {}
};
typedef Point Vector;
Point operator + (Point a, Point b) { return Point(a.x+b.x, a.y+b.y); }
Point operator - (Point a, Point b) { return Point(a.x-b.x, a.y-b.y); }
Vector operator * (Vector a, double p) { return Vector(a.x*p, a.y*p); }
Vector operator / (Vector a, double p) { return Vector(a.x/p, a.y/p); }
bool operator < (const Point& a, const Point& b)
{ return a.x < b.x || (a.x == b.x && a.y < b.y); }
bool operator == (const Point& a, const Point& b)
{ return a.x == b.x && a.y == b.y; }
double Dot(const Vector& a, const Vector& b) { return a.x*b.x + a.y*b.y; }
double Cross(const Vector& a, const Vector& b) { return a.x*b.y - a.y*b.x; }
double Length(const Vector& a) { return sqrt(Dot(a, a)); }
Vector Normal(const Vector& a)
{
double l = Length(a);
return Vector(-a.y/l, a.x);
} double PolygonArea(const vector<Point>& p)
{
int n = p.size();
double ans = 0.0;
for(int i = ; i < n-; ++i)
ans += Cross(p[i]-p[], p[i+]-p[]);
return ans/;
} struct Line
{
Point P;
Vector v;
double ang;
Line() {}
Line(Point p, Vector v):P(p), v(v) { ang = atan2(v.y, v.x); }
bool operator < (const Line& L) const
{
return ang < L.ang;
}
}; bool OnLeft(const Line& L, Point p)
{
return Cross(L.v, p-L.P) > ;
} Point GetLineIntersevtion(const Line& a, const Line& b)
{
Vector u = a.P - b.P;
double t = Cross(b.v, u) / Cross(a.v, b.v);
return a.P + a.v*t;
} vector<Point> HalfplaneIntersection(vector<Line> L)
{
int n = L.size();
sort(L.begin(), L.end()); int first, last;
vector<Point> p(n);
vector<Line> q(n);
vector<Point> ans; q[first=last=] = L[];
for(int i = ; i < n; ++i)
{
while(first < last && !OnLeft(L[i], p[last-])) last--;
while(first < last && !OnLeft(L[i], p[first])) first++;
q[++last] = L[i];
if(fabs(Cross(q[last].v, q[last-].v)) < eps)
{
last--;
if(OnLeft(q[last], L[i].P)) q[last] = L[i];
}
if(first < last) p[last-] = GetLineIntersevtion(q[last-], q[last]);
}
while(first < last && !OnLeft(q[first], p[last-])) last--;
if(last - first <= ) return ans;
p[last] = GetLineIntersevtion(q[first], q[last]); for(int i = first; i <= last; ++i) ans.push_back(p[i]);
return ans;
} int main(void)
{
#ifdef LOCAL
freopen("2218in.txt", "r", stdin);
#endif int n;
while(scanf("%d", &n) == && n)
{
for(int i = ; i < n; ++i) scanf("%d%d%d", &v[i], &u[i], &w[i]);
for(int i = ; i < n; ++i)
{
int ok = ;
double k = ;
vector<Line> L;
for(int j = ; j < n; ++j) if(j != i)
{
if(v[i]<=v[j] && u[i]<=u[j] && w[i]<=w[j]) { ok = ; break; }
if(v[i]>v[j] && u[i]>u[j] && w[i]>w[j]) continue; double a = (k/v[j]-k/v[i]+k/w[i]-k/w[j]);
double b = (k/u[j]-k/u[i]+k/w[i]-k/w[j]);
double c = k/w[j]-k/w[i];
//L.push_back(Line(Point(0, -c/b), Vector(b, -a)));
Point P;
Vector V(b, -a);
if(fabs(a) > fabs(b)) P = Point(-c/a, );
else P = Point(, -c/b);
L.push_back(Line(P, V));
}
if(ok)
{
L.push_back(Line(Point(, ), Vector(, -)));
L.push_back(Line(Point(, ), Vector(, )));
L.push_back(Line(Point(, ), Vector(-, )));
vector<Point> Poly = HalfplaneIntersection(L);
if(Poly.empty()) ok = ;
}
if(ok) puts("Yes"); else puts("No");
}
} return ;
}
代码君