题目大意：
铁人三项分连续三段：游泳 自行车 赛跑
已知各选手在每个单项中的速度v[i],u[i],w[i]
设计每个单项的长度 可以让某个特定的选手获胜
判断哪些选手有可能获得冠军
输出n行 有可能获得冠军为Yes 不可能为No
设赛程总长为1，游泳x 自行车y，则赛跑为1-x-y
若选手 i 可以打败选手 j 则
x / v[ i ] + y / u[ i ] + ( 1-x-y ) / w[ i ] < x / v[ j ] + y / u[ j ] + ( 1-x-y ) / w[ j ]
整理成 a*x+b*y+c >0 的形式 那么得到
a = ( 1 / v[ j ] - 1 / w[ j ] ) - ( 1 / v[ i ] - 1 / w[ i ] )
b = ( 1 / u[ j ] - 1 / w[ j ] ) - ( 1 / u[ i ] - 1 / w[ i ] )
c = 1 / w[ j ] - 1 / w[ i ]
最后加上三个固定约束
x > 0 , y > 0 , 1 - x - y > 0
只要 i 与其他所有 j 存在满足的解 就为Yes
#include <bits/stdc++.h>
using namespace std; const double eps=1e-;
double add(double a,double b) {
if(abs(a+b)<eps*(abs(a)+abs(b))) return ;
return a+b;
}
struct P {
double x,y;
P(){}
P(double _x,double _y):x(_x),y(_y){}
P operator - (P p) {
return P(add(x,-p.x),add(y,-p.y)); }
P operator + (P p) {
return P(add(x,p.x),add(y,p.y)); }
P operator / (double d) {
return P(x/d,y/d); }
P operator * (double d) {
return P(x*d,y*d); }
double dot (P p) {
return add(x*p.x,y*p.y); }
double det (P p) {
return add(x*p.y,-y*p.x); }
void read(){
scanf("%lf%lf",&x,&y); }
};
struct L {
P p,v;
double ang;
L(){}
L(P _p,P _v):p(_p),v(_v){ ang=atan2(v.y,v.x); }
bool operator < (const L& b)const {
return ang<b.ang;
}
}l[];
int v[],u[],w[];
int n, cnt; bool onLeft(L l,P p) {
return (l.v).det(p-l.p)>;
} /// p在l的左边
P ins(L a,L b) {
return a.p+a.v*((b.v).det(a.p-b.p)/(a.v).det(b.v));
} /// a与b的交点
int insHp() {
sort(l,l+cnt); vector <P> pi(*cnt);
vector <L> li(*cnt);
int head,tail;
li[head=tail=]=l[];
for(int i=;i<cnt;i++) {
while(head<tail && !onLeft(l[i],pi[tail-])) tail--;
while(head<tail && !onLeft(l[i],pi[head])) head++;
li[++tail]=l[i]; if(abs((li[tail].v).det(li[tail-].v))<eps) {
tail--;
if(onLeft(li[tail],l[i].p)) li[tail]=l[i];
}
if(head<tail) pi[tail-]=ins(li[tail],li[tail-]);
}
while(head<tail && !onLeft(li[head],pi[tail-])) tail--; if(tail-head<=) return ;
pi[tail]=ins(li[tail],li[head]); return tail-head+;
} /// 半平面交 返回最后得到的多边形的顶点数 void solve() {
for(int i=;i<n;i++) {
cnt=;
bool ok=;
double k=; /// 数据范围来说 设k=10000 for(int j=;j<n;j++) {
if(i==j) continue;
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/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]; /// 数值过小会产生精度误差
P v=P(b,-a);
if(abs(a)>abs(b)) l[cnt]=L(P(-c/a,),v);
else l[cnt]=L(P(,-c/b),v);
cnt++;
}
if(ok) {
l[cnt++]=L(P(,),P(,-));
l[cnt++]=L(P(,),P(,));
l[cnt++]=L(P(,),P(-,)); // 三个固定约束
if(!insHp()) ok=; // 半平面交无解 说明必败
}
if(ok) printf("Yes\n");
else printf("No\n");
}
} int main()
{
while(~scanf("%d",&n)) {
for(int i=;i<n;i++)
scanf("%d%d%d",&v[i],&u[i],&w[i]);
solve();
} return ;
} //