POJ 3335 Rotating Scoreboard(多边形的核)

我看的这里：http://www.cnblogs.com/ka200812/archive/2012/01/20/2328316.html

然后整理一下当做模版。0换成eps，会wa，应该要写成精度特判把。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <string>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 #define eps 1e-8
 8 #define N 110
 9 struct point
10 {
11     double x,y;
12 }p[N],temp[N],pre[N];
13 int n,m;
14 double a,b,c;
15 void getline(point x,point y)
16 {
17     a = y.y - x.y;
18     b = x.x - y.x;
19     c = y.x * x.y - x.x * y.y;
20 }
21 point intersect(point x,point y) //获取直线ax+by+c==0  和点x和y所连直线的交点
22 {
23     double u = fabs(a*x.x+b*x.y+c);
24     double v = fabs(a*y.x+b*y.y+c);
25     point ans;
26     ans.x = (x.x*v+y.x*u)/(u+v);
27     ans.y = (x.y*v+y.y*u)/(u+v);
28     return ans;
29 }
30 void cut()
31 {
32     int num = 0,i;
33     for(i = 1;i <= m;i ++)
34     {
35         if(a*p[i].x + b*p[i].y + c >= 0)
36         {
37             temp[++num] = p[i];
38         }
39         else
40         {
41             if(a*p[i-1].x + b*p[i-1].y + c > 0)
42             temp[++num] = intersect(p[i],p[i-1]);
43             if(a*p[i+1].x + b*p[i+1].y + c > 0)
44             temp[++num] = intersect(p[i],p[i+1]);
45         }
46     }
47     for(i = 1;i <= num;i ++)
48     p[i] = temp[i];
49     p[0] = p[num];
50     p[num+1] = p[1];
51     m = num;
52 }
53 void fun()
54 {
55     int i;
56     m = n;
57     for(i = 1;i <= n;i ++)
58     {
59         getline(pre[i],pre[i+1]);
60         cut();
61     }
62 }
63 int main()
64 {
65     int i,t;
66     scanf("%d",&t);
67     while(t--)
68     {
69         scanf("%d",&n);
70         for(i = 1;i <= n;i ++)
71         {
72             scanf("%lf%lf",&pre[i].x,&pre[i].y);
73             p[i] = pre[i];
74         }
75         pre[n+1] = pre[1];
76         p[n+1] = p[1];
77         p[0] = p[n];
78         fun();
79         if(m)
80         printf("YES
");
81         else
82         printf("NO
");
83     }
84     return 0;
85 }