poj 2653 计算几何

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <cstdio>
 6 using namespace std;
 7 struct  point {
 8     double x,y;
 9 };
10 point be[100005],en[100005];
11 int ans[100005];
12 int res[100005];
13 
14 double max(double a,double b){
15     return a>b?a:b;
16 }
17 double min(double a,double b){
18     return a<b?a:b;
19 }
20 
21 int inter(point a,point b,point c,point d){
22     if(min(a.x,b.x)>max(c.x,d.x)||min(a.y,b.y)>max(c.y,d.y)||min(c.x,d.x)>max(a.x,b.x)||min(c.y,d.y)>max(a.y,b.y))
23         return 0;
24     double h,i,j,k;
25     h = (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);
26     i = (d.x-a.x)*(b.y-a.y)-(d.y-a.y)*(b.x-a.x);
27     j = (a.x-c.x)*(d.y-c.y)-(a.y-c.y)*(d.x-c.x);
28     k = (b.x-c.x)*(d.y-c.y)-(b.y-c.y)*(d.x-c.x);
29     return h*i<0&&j*k<0;
30 }
31 int main()
32 {
33     int n;
34     while(scanf("%d",&n)==1&&n){
35         for(int i=0;i<n;i++)
36             cin>>be[i].x>>be[i].y>>en[i].x>>en[i].y;
37         memset(ans,0,sizeof(ans));
38         memset(res,0,sizeof(res));
39         for(int i=0;i<n;i++){
40             for(int j=i+1;j<n;j++){
41                 if(inter(be[i],en[i],be[j],en[j])){
42                     ans[i] =1;
43                     break;
44                 }
45             }
46         }
47         int cnt =0;
48         for(int i=0;i<n;i++){
49             if(!ans[i])
50                 res[cnt++] = i+1;
51         }
52         printf("Top sticks: ");
53         for(int i=0;i<cnt-1;i++)
54             printf("%d, ",res[i]);
55         printf("%d.
",res[cnt-1]);
56 
57     }
58     return 0;
59 }