计算几何LA2218HPI第一次卡精度vijos1087铁人三项

This article is made by Jason-Cow.
Welcome to reprint.
But please post the writer's address.

http://www.cnblogs.com/JasonCow/

LA2218 && vijos1087铁人三项

描述

所有运动员的3个项目的速度都是已知的。裁判可以任意规定每一个项目的路程长度，并且每个项目的长度均为正数。

正因为裁判拥有如此大的权力，所以有些运动员会贿赂裁判，让他规定对自己有利的各项目的路程长度，而使自己获得第一名。但并非每个人都有这样的机会。有些运动员因为实力实在太差，以致无论裁判规定怎样的长度，都无法获得第一名。现在请你来判断，每一位运动员是否有可能通过贿赂裁判获得第一名（不能是并列第一）。

格式

输入格式

首行为运动员的人数N (1<=N<=100)，以下N行，每行含3个整数，Vi，Ui和Wi(1<=Vi，Ui，Wi<=10000)，用空格隔开，表示各人3个项目的速度。

输出格式

对于每个运动员，输出一行，如果他能通过贿赂裁判获得第一名，则输出“Yes”，否则输出“No”。

样例

样例输入

样例输出

Yes
Yes
Yes
No
No
No
Yes
No
Yes

一眼简单线性规划嘛！谁看不出来？！数学必修5

推方程。Let go!

设总长为‘1’，三短距离分别为 x , y , (1-x-y)

i战胜j：

　　 $\frac{x}{v[i]}+\frac{y}{u[i]}+\frac{1-x-y}{w[i]}<\frac{x}{v[j]}+\frac{y}{u[j]}+\frac{1-x-y}{w[j]}$

　　 $Ax+By+C>0$

　　 $\left\{\begin{matrix} & A=(\frac{1}{v[j]}-\frac{1}{w[j]})-(\frac{1}{v[i]}-\frac{1}{w[i]}) & \\ & B=(\frac{1}{u[j]}-\frac{1}{w[j]})-(\frac{1}{u[i]}-\frac{1}{w[i]}) & \\ & C=(\frac{1}{w[j]}-\frac{1}{w[i]}) \end{matrix}\right.$

注意精度的问题（对a/b 和 a/c 若|b|>|c| 则a/b优于a/c???）：

1 D P;
2 if(fabs(A)>fabs(B))P=D(-C/A,0);
3 else               P=D(0,-C/B);
4 l[++cnt]=L(P,V(B,-A));//Ax+By+C>0

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <cstdio>
  6 #include <vector>
  7 #include <cmath>
  8 #include <queue>
  9 #include <map>
 10 #include <set>
 11 using namespace std;
 12 #define sqr(x) ((x)*(x))
 13 #define RG register
 14 #define op operator
 15 #define IL inline
 16 typedef double db;
 17 typedef bool bl;
 18 const db pi=acos(-1.0),eps=1e-10;
 19 struct D{
 20   db x,y;
 21   D(db x=0.0,db y=0.0):x(x),y(y){}
 22 };
 23 typedef D V;
 24 bl operator<(D A,D B){return A.x<B.x||(A.x==B.x&&A.y<B.y);}
 25 V operator+(V A,V B){return V(A.x+B.x,A.y+B.y);}
 26 V operator-(V A,V B){return V(A.x-B.x,A.y-B.y);}
 27 V operator*(V A,db N){return V(A.x*N,A.y*N);}
 28 V operator/(V A,db N){return V(A.x/N,A.y/N);}
 29 
 30 db dcmp(db x){if(fabs(x)<eps)return 0;return x<0?-1:1;}
 31 db Ang(db x){return(x*180.0/pi);}
 32 db Rad(db x){return(x*pi/180.0);}
 33 V Rotate(V A,db a){return V(A.x*cos(a)-A.y*sin(a),A.x*sin(a)+A.y*cos(a));}
 34 db Dis(D A,D B){return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));}
 35 db Cross(V A,V B){return A.x*B.y-A.y*B.x;}
 36 
 37 struct L{
 38   D P,v;db a;
 39   L(){}
 40   L(D P,V v):P(P),v(v){a=atan2(v.y,v.x);}
 41   bl operator<(const L x)const{return a<x.a;}
 42 };
 43 
 44 D Intersect(L a,L b){
 45   V u=a.P-b.P;
 46   return a.P+a.v*(Cross(b.v,u)/Cross(a.v,b.v));
 47 }
 48 
 49 bl Left(L l,D A){return Cross(l.v,A-l.P)>0;}
 50 
 51 int HPI(L*l,int n,D*ans){
 52   int head,tail,m=0;D*P=new D[n];L*q=new L[n];
 53   sort(l+1,l+n+1),q[head=tail=0]=l[1];
 54   for(int i=2;i<=n;i++){
 55     while(head<tail && !Left(l[i],P[tail-1]))tail--;
 56     while(head<tail && !Left(l[i],P[head]))  head++;
 57     q[++tail]=l[i];
 58     if(fabs(Cross(q[tail].v,q[tail-1].v))<eps){
 59       tail--;
 60       if(Left(q[tail],l[i].P))q[tail]=l[i];
 61     }
 62     if(head<tail)P[tail-1]=Intersect(q[tail-1],q[tail]);
 63   }
 64   while(head<tail && !Left(q[head],P[tail-1]))tail--;
 65   if(tail-head<=1)return 0;
 66   P[tail]=Intersect(q[tail],q[head]);
 67   for(int i=head;i<=tail;i++)ans[++m]=P[i];
 68   return m;
 69 }
 70 
 71 const int maxn=100+10;
 72 const db K=1;//解决精度问题，技巧1
 73 int n;L l[maxn];D A[maxn];
 74 int u[maxn],v[maxn],w[maxn];
 75 db a[maxn],b[maxn],c[maxn];
 76 
 77 int main(){
 78   while(scanf("%d",&n)!=EOF&&n){
 79     for(int i=1;i<=n;i++)scanf("%d%d%d",&v[i],&u[i],&w[i]);
 80     for(int i=1;i<=n;i++)a[i]=K/v[i]-K/w[i],b[i]=K/u[i]-K/w[i],c[i]=K/w[i];
 81     for(int i=1;i<=n;i++){
 82       int ok=true,cnt=0;
 83       for(int j=1;j<=n;j++){
 84         if(i==j)continue;
 85         if(v[i]<=v[j] && u[i]<=u[j] && w[i]<=w[j]){ok=0;break;}
 86         if(v[i]> v[j] && u[i]> u[j] && w[i]> w[j])continue;
 87         db A=a[j]-a[i],B=b[j]-b[i],C=c[j]-c[i];
 88         D P;//解决精度问题，技巧2
 89         if(fabs(A)>fabs(B))P=D(-C/A,0);
 90         else               P=D(0,-C/B);
 91         l[++cnt]=L(P,V(B,-A));//Ax+By+C>0
 92       }
 93       if(ok){//x>0 y>0 1-x-y>0
 94         l[++cnt]=L(D(0,0),V(0,-1));
 95         l[++cnt]=L(D(0,0),V(1,0));
 96         l[++cnt]=L(D(1,0),V(-1,1));
 97         ok=HPI(l,cnt,A)?true:false;
 98       }
 99       printf("%s\n",ok?"Yes":"No");
100     }
101   }
102   return 0;
103 }

~~Jason_liu O(∩_∩)O