uva 2218 Triathlon

时间:2022-12-31 19:22:58

题意:铁人三项赛,给定每个选手游泳,自行车,赛跑三个阶段的平均速度,不知道每段比赛的路程,询问当前这个选手能否胜利。

思路:把题意转化为一个不等式,设比赛长度是1,如果i要战胜j,x、y分别是第一阶段和第二阶段的比赛长度: (x / ui + y / vi + (1-x-y) / wi) < (x / uj + y / vj + (1-x-y) / wj) 可以转化为Ax + By + C > 0的形式,也就可以用半平面交来解决,对于每个i都有其他n-1个j的半平面和x>0, y>0, (1-x-y)>0这三个半平面,如果这些半平面(n+2)都有交集,说明i有可能打败其他选手,否则不可能。

此题值得注意的是精度问题,选P点时(L上的一点),如果默认P=Point(-c/a,0),能过,但是只是P = Point(0, -c/b),就不行了。计算几何一点要注意精度问题!!!

 #include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<memory.h>
#include<cstdlib>
#include<vector>
#define clc(a,b) memset(a,b,sizeof(a))
#define LL long long int
#define up(i,x,y) for(i=x;i<=y;i++)
#define w(a) while(a)
const double inf=0x3f3f3f3f;
const int N = ;
const double eps = *1e-;
const double PI = acos(-1.0);
using namespace std; struct Point
{
double x, y;
Point(double x=, double y=):x(x),y(y) { }
}; typedef Point Vector; Vector operator + (const Vector& A, const Vector& B)
{
return Vector(A.x+B.x, A.y+B.y);
}
Vector operator - (const Point& A, const Point& B)
{
return Vector(A.x-B.x, A.y-B.y);
}
Vector operator * (const Vector& A, double p)
{
return Vector(A.x*p, A.y*p);
}
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/L);
} double PolygonArea(vector<Point> p)
{
int n = p.size();
double area = ;
for(int i = ; i < n-; i++)
area += Cross(p[i]-p[], p[i+]-p[]);
return area/;
} // 有向直线。它的左边就是对应的半平面
struct Line
{
Point P; // 直线上任意一点
Vector v; // 方向向量
double ang; // 极角,即从x正半轴旋转到向量v所需要的角(弧度)
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;
}
}; // 点p在有向直线L的左边(线上不算)
bool OnLeft(const Line& L, const Point& p)
{
return Cross(L.v, p-L.P) > ;
} // 二直线交点,假定交点惟一存在
Point GetLineIntersection(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;
} const double INF = 1e8; // 半平面交主过程
vector<Point> HalfplaneIntersection(vector<Line> L)
{
int n = L.size();
sort(L.begin(), L.end()); // 按极角排序 int first, last; // 双端队列的第一个元素和最后一个元素的下标
vector<Point> p(n); // p[i]为q[i]和q[i+1]的交点
vector<Line> q(n); // 双端队列
vector<Point> ans; // 结果 q[first=last=] = L[]; // 双端队列初始化为只有一个半平面L[0]
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-] = GetLineIntersection(q[last-], q[last]);
}
while(first < last && !OnLeft(q[first], p[last-])) last--; // 删除无用平面
if(last - first <= ) return ans; // 空集
p[last] = GetLineIntersection(q[last], q[first]); // 计算首尾两个半平面的交点 // 从deque复制到输出中
for(int i = first; i <= last; i++) ans.push_back(p[i]);
return ans;
} const int maxn = + ;
int V[maxn], U[maxn], W[maxn];
int main()
{
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(i != j)
{
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;
// x/V[i]+y/U[i]+(1-x-y)/W[i] < x/V[j]+y/U[j]+(1-x-y)/W[j]
// ax+by+c>0
double a = (k/V[j]-k/W[j]) - (k/V[i]-k/W[i]);
double b = (k/U[j]-k/W[j]) - (k/U[i]-k/W[i]);
double c = k/W[j] - k/W[i];
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)
{
// x>0, y>0, x+y<1 ==> -x-y+1>0
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) printf("Yes\n");
else printf("No\n");
}
}
return ;
}