uva 1298

半平面交的题；
这个题目的亮点就是建模；
  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cmath>
  4 #define maxn 109
  5 #define eps 1e-6
  6 using namespace std;
  7 
  8 int dcmp(double x)
  9 {
 10     return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1);
 11 }
 12 
 13 struct Point
 14 {
 15     double x;
 16     double y;
 17     Point(double x = 0, double y = 0):x(x), y(y) {}
 18 };
 19 typedef Point Vector;
 20 
 21 Vector operator + (Point A, Point B)
 22 {
 23     return Vector(A.x + B.x, A.y + B.y);
 24 }
 25 
 26 Vector operator - (Point A, Point B)
 27 {
 28     return Vector(A.x - B.x, A.y - B.y);
 29 }
 30 
 31 Vector operator * (Point A, double p)
 32 {
 33     return Vector(A.x * p, A.y * p);
 34 }
 35 
 36 Vector operator / (Point A, double p)
 37 {
 38     return Vector(A.x / p, A.y / p);
 39 }
 40 double dot(Point a,Point b)
 41 {
 42     return a.x*b.x+a.y*b.y;
 43 }
 44 double cross(Point a,Point b)
 45 {
 46     return a.x*b.y-a.y*b.x;
 47 }
 48 
 49 Vector nomal(Vector a)
 50 {
 51     double l=sqrt(dot(a,a));
 52     return Vector(-a.y/l,a.x/l);
 53 }
 54 
 55 struct line
 56 {
 57     Point p;
 58     Vector v;
 59     double ang;
 60     line() {}
 61     line(Point p,Vector v):p(p),v(v)
 62     {
 63         ang=atan2(v.y,v.x);
 64     }
 65     bool operator<(const line &t)const
 66     {
 67         return ang<t.ang;
 68     }
 69 };
 70 
 71 bool onleft(line l,Point p)
 72 {
 73     return (cross(l.v,p-l.p)>0);
 74 }
 75 
 76 Point getintersection(line a,line b)
 77 {
 78     Vector u=a.p-b.p;
 79     double t=cross(b.v,u)/cross(a.v,b.v);
 80     return a.p+a.v*t;
 81 }
 82 
 83 int halfplanintersection(line *l,int n,Point *poly)
 84 {
 85     sort(l,l+n);
 86     int first,last;
 87     Point *p=new Point[n];
 88     line *q=new line[n];
 89     q[first=last=0]=l[0];
 90     for(int i=1; i<n; i++)
 91     {
 92         while(first<last && !onleft(l[i],p[last-1]))last--;
 93         while(first<last && !onleft(l[i],p[first]))first++;
 94         q[++last]=l[i];
 95         if(fabs(cross(q[last].v,q[last-1].v))<eps)
 96         {
 97             last--;
 98             if(onleft(q[last],l[i].p))q[last]=l[i];
 99         }
100         if(first<last)p[last-1]=getintersection(q[last-1],q[last]);
101     }
102     while(first<last && !onleft(q[first],p[last-1]))last--;
103     if((last-first )<=1)return 0;
104     p[last]=getintersection(q[last],q[first]);
105     int m=0;
106     for(int i=first; i<=last; i++)poly[m++]=p[i];
107     return m;
108 }
109 
110 Point poly[maxn];
111 line l[maxn];
112 double v[maxn],u[maxn],w[maxn];
113 
114 int main()
115 {
116     int n;
117     while(scanf("%d",&n)!=EOF)
118     {
119         for(int i=0;i<n;i++)scanf("%lf%lf%lf",&v[i],&u[i],&w[i]);
120         for(int i=0;i<n;i++)
121         {
122             double k=10000;
123             bool flag=1;
124             int cnt=0;
125             for(int j=0;j<n;j++)
126             {
127                 if(i==j)continue;
128                 if(v[j]>=v[i]&&u[j]>=u[i]&&w[j]>=w[i]){flag=0;break;}
129                 if(v[j]<=v[i]&&w[j]<=u[i]&&w[j]<=w[i])continue;
130                 double a=(k/v[j]-k/w[j])-(k/v[i]-k/w[i]);
131                 double b=(k/u[j]-k/w[j])-(k/u[i]-k/w[i]);
132                 double c=k/w[j]-k/w[i];
133                 Point p;
134                 Vector v(b,-a);
135                 if(fabs(a)>fabs(b))p=Point(-c/a,0);
136                 else p=Point(0,-c/b);
137                 l[cnt++]=line(p,v);
138             }
139             if(flag)
140             {
141                 l[cnt++]=line(Point(0,0),Vector(0,-1));
142                 l[cnt++]=line(Point(0,0),Vector(1,0));
143                 l[cnt++]=line(Point(0,1),Vector(-1,1));
144                 if(halfplanintersection(l,cnt,poly)==0)flag=0;
145             }
146             if(flag)puts("Yes");
147             else puts("No");
148         }
149 
150     }return 0;
151 }
View Code