http://poj.org/problem?id=3130
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #define maxn 1000000 6 using namespace std; 7 8 const double eps=(1e-8); 9 struct point 10 { 11 double x,y; 12 }; 13 double a,b,c; 14 int n,cutt=0,m; 15 point p1[maxn]; 16 point p2[maxn]; 17 point p3[maxn]; 18 19 void get(point c1,point c2) 20 { 21 a=c2.y-c1.y; 22 b=c1.x-c2.x; 23 c=c1.y*c2.x-c1.x*c2.y; 24 } 25 26 point insertsect(point c1,point c2) 27 { 28 double u=fabs(a*c1.x+b*c1.y+c); 29 double v=fabs(a*c2.x+b*c2.y+c); 30 point p; 31 p.x=(c1.x*v+c2.x*u)/(u+v); 32 p.y=(c1.y*v+c2.y*u)/(u+v); 33 return p; 34 } 35 36 void cut() 37 { 38 int cutnum=0; 39 for(int i=1; i<=m; i++) 40 { 41 if(a*p3[i].x+b*p3[i].y+c>=0) 42 p2[++cutnum]=p3[i]; 43 else 44 { 45 if(a*p3[i-1].x+b*p3[i-1].y+c>0) 46 p2[++cutnum]=insertsect(p3[i-1],p3[i]); 47 if(a*p3[i+1].x+b*p3[i+1].y+c>0) 48 p2[++cutnum]=insertsect(p3[i+1],p3[i]); 49 } 50 } 51 for(int i=1; i<=cutnum; i++) 52 p3[i]=p2[i]; 53 p3[cutnum+1]=p2[1]; p3[0]=p2[cutnum]; 54 m=cutnum; 55 } 56 57 58 int main() 59 { 60 while(scanf("%d",&n)!=EOF) 61 { 62 if(n==0) break; 63 for(int i=1; i<=n; i++) 64 { 65 scanf("%lf%lf",&p1[i].x,&p1[i].y); 66 } 67 for(int i=1; i<(n+1)/2; i++) 68 { 69 swap(p1[i],p1[n-i]); 70 } 71 for(int i=1; i<=n; i++) 72 { 73 p3[i]=p1[i]; 74 } 75 p1[n+1]=p1[1]; 76 p3[n+1]=p3[1]; 77 p3[0]=p3[n]; 78 m=n; 79 for(int i=1; i<=n; i++) 80 { 81 get(p1[i],p1[i+1]); 82 cut(); 83 } 84 if(m==0) printf("0 "); 85 else printf("1 "); 86 } 87 return 0; 88 }