poj 1755 Triathlon 半平面交判断不等式是否有解

有一个全能运动必有要求运动员完成游泳、骑自行车、跑步，三个项目。冠军为最快完成所有项目的运动员。已知每个运动员的三项速度分别为Vi, Ui, Wi 。裁判能够任意的设置三个项目的路程。问对某个运动员能否设定一个让他必羸的路程设置。

当构造一个a，b，c的距离，使得t = a/u + b/v + c/w 时间最小，就可以了
   那么就可以转化成 (1 / u1 - 1 / u2) * a + (1 / v1 - 1 / v2) * b + (1 / w1 - 1 / w2) * c < 0
   ==> (1 / u1 - 1 / u2) * a / c + (1 / v1 - 1 / v2) * b / c + (1 / w1 - 1 / w2) < 0
   ==> 符合 a * x + b * y + c < 0这样子直接用半平面交求就行了，如果不能构成一个核（点数少于3），就表示无解
   构造不等式 ax + by + c < 0;
   这里具体问题具体分析吧，反正把所有不等式构造成符号同一个方向就行了,然后再把cut函数里面的判断符号也改了

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<math.h>
 4 const double inf=1e20;
 5 const double eps=1e-10;
 6 const int N=105;int n,sz;
 7 double u[N],v[N],w[N];
 8 struct point
 9 {
10     double x,y;
11 }p[N],q[N];
12 void init()
13 {   
14     sz = 4;
15     p[1].x=p[1].y=0;
16     p[2].x=inf, p[2].y=0;   
17     p[3].x=p[3].y=inf;   
18     p[4].x=0, p[4].y=inf;  
19     p[0]=p[4], p[5]=p[1];  
20 } 
21 int dcmp(double x)
22 {   
23     if (x < -eps)  
24         return -1; 
25     else  
26         return (x > eps);     
27 }
28 point intersect(const point &p1, const point &p2, double a, double b, double c)
29 {
30     point g;
31     double u = fabs(a * p1. x + b * p1. y + c);   
32     double v = fabs(a * p2. x + b * p2. y + c);   
33     g.x=(p1.x*v + p2.x*u)/(u+v),g.y=(p1.y*v+p2.y*u)/(u+v);   
34     return g;
35 }     
36 void cut(double a, double b, double c)
37 {   
38     int s = 0,i;   
39     for ( i = 1; i <= sz; i++)
40     {    
41         if (dcmp(a * p[i]. x + b * p[i]. y + c) <=0)     
42             q[++s] = p[i];    
43         else 
44         {     
45             if (dcmp(a * p[i - 1]. x + b * p[i - 1]. y + c) < 0)      
46                 q[++s] = intersect(p[i-1], p[i], a, b, c);     
47             if (dcmp(a * p[i + 1]. x + b * p[i + 1]. y + c) < 0)      
48                 q[++s] = intersect(p[i], p[i+1], a, b, c);    
49         }   
50     }
51     for ( i = 1; i <= s; i++) 
52         p[i] = q[i];    
53     p[s+1] = p[1];
54     p[0] = p[s];   
55     sz = s;  
56 }
57 int solve(int x)
58 {
59     int i;
60     for (i=0; i<n;i++) 
61     { 
62         if (i!=x&&u[x]<=u[i]&&v[x]<=v[i]&&w[x]<=w[i])   
63             return 0;
64     }
65     init();   
66     for ( i = 0; i < n; i++) 
67     { 
68         if (i != x) 
69         {        
70             double a = 1/u[x] - 1/u[i], b = 1/v[x] - 1/v[i], c = 1/w[x] - 1/w[i];      
71             cut(a, b, c);     
72             if (sz < 3)   
73                 return 0;     
74         }  
75     }    
76     return (sz > 2);
77 }
78 int main()
79 {
80     int i;
81     scanf("%d",&n);
82     for(i=0;i<n;i++) 
83         scanf("%lf %lf %lf",&u[i],&v[i],&w[i]);
84     for(i=0;i<n;i++)
85     { 
86         if(solve(i))  
87             printf("Yes\n"); 
88         else  
89             printf("No\n");
90     }
91     system("pause");
92     return 0;
93 }