poj 3130

半平面交，求解多变形内核的问题感觉一个讲的很清晰的链接 http://www.cnblogs.com/ka200812/archive/2012/01/20/2328316.html

首先说一下什么是多边形内核，内核是一个点集，该集合内的任意一个点与简单多边形边界上一点的连线都在简单多变形内，也可以说集合内任意一点都可以看见该多边行内的任何一个地方。

求解多边形内核的方法是用多边形的两个顶点组成的线段不断的去切割多边形，切割到最后剩下的，就是内核区间了。

一条直线可以将平面切割成两个区域，假设直线方程为

ax+by+c==0，那么，两个平面可分别表示成ax+by+c>=0 和 ax+by+c<0两部分，

求解步骤:

1，用一个顺时针或者逆时针的顺序，将最初的多边形的点集储存起来。

2，按顺序取连续的两个点组成一条直线，用这条直线来切割原先的多边形 (本题是逆时针输入的）如果多边形的点到在直线的一侧，则不用管，如果直线把多边形切成了两部分，那么多边形顶点集就要更新为直线的交点

3，重复操作2，遍历所有的顶点

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <algorithm>
 6 #include <set>
 7 #include <vector>
 8 #include <map>
 9 #include <math.h>
10 #define _clr(a,val) (memset(a,val,sizeof(a)))
11 #define Max(x,y) (x) < (y) ? (y):(x)
12 #define Min(x,y) (x) < (y) ? (x):(y)
13 #define Mid(x,y) (((x) + (y)) >> 1)
14 
15 using namespace std;
16 
17 const int N = 60;
18 const double esp = 1e-8;
19 typedef long long ll;
20 struct node
21 {
22     double x;
23     double y;
24 };
25 node tp[N],p[N],t[N];
26 int num,tnum;
27 double a,b,c;
28 int juge(double k)
29 {
30     return (k < -esp) ? -1 : (k > esp);
31 }
32 void insert(node n,node m)
33 {
34     node tt;
35     double tx = fabs(a * n.x + b * n.y + c);
36     double ty = fabs(a * m.x + b * m.y + c);
37     tt.x = (n.x * ty + m.x * tx) / (tx + ty);
38     tt.y = (n.y * ty + m.y * tx) / (tx + ty);
39     t[++tnum] = tt;
40 
41 }
42 void solve()
43 {
44     tnum = 0;
45     int i;
46     for(i = 1; i <= num; i++)
47     {
48         if(juge(a * tp[i].x + b * tp[i].y + c) <= 0)  // 直线分割如果在直线的一侧，那么直接保存点
49         {
50             t[++tnum] = tp[i];
51         }
52         else  // 如果分成了两部分，则要保存交点
53         {
54             if(juge(a * tp[i - 1].x + b * tp[i - 1].y + c) < 0)
55             insert(tp[i - 1],tp[i]);
56             if(juge(a * tp[i + 1].x + b * tp[i + 1].y + c) < 0)
57             insert(tp[i + 1],tp[i]);
58         }
59     }
60 
61     for(i = 1; i <= tnum; i++)  // 更新辅助数组
62     tp[i] = t[i];
63     tp[0] = tp[tnum], tp[tnum + 1] = tp[1];
64     num = tnum;
65 }
66 int main()
67 {
68     int i,n;
69     //freopen("data.txt","r",stdin);
70     while(scanf("%d",&n), n)
71     {
72         for(i = 0; i < n; i++)
73         {
74             scanf("%lf%lf",&p[i].x,&p[i].y);
75             tp[i + 1] = p[i];
76         }
77 
78         p[n] = p[0];
79         tp[0] = tp[n], tp[n + 1] = tp[1];
80         num = n;
81         for(i = 0; i < n; i++)  // 遍历所有的顶点
82         {
83             a = p[i + 1].y - p[i].y;
84             b = p[i].x - p[i + 1].x;
85             c = p[i + 1].x * p[i].y - p[i + 1].y * p[i].x;
86             solve();
87         }
88         if(!num) printf("0\n");  // 如果num为零则说明没有核
89         else printf("1\n");
90     }
91     return 0;
92 }

题目：http://poj.org/problem?id=3335

一模一样的题，这个是顺时针输入的，上个题目是逆时针输入的

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <algorithm>
 6 #include <set>
 7 #include <vector>
 8 #include <map>
 9 #include <math.h>
10 #define _clr(a,val) (memset(a,val,sizeof(a)))
11 #define Max(x,y) (x) < (y) ? (y):(x)
12 #define Min(x,y) (x) < (y) ? (x):(y)
13 #define Mid(x,y) (((x) + (y)) >> 1)
14 
15 using namespace std;
16 
17 const int N = 110;
18 const double esp = 1e-8;
19 typedef long long ll;
20 struct node
21 {
22     double x;
23     double y;
24 };
25 node tp[N],p[N],t[N];
26 int num,tnum;
27 double a,b,c;
28 int juge(double k)
29 {
30     return (k < -esp) ? -1 : (k > esp);
31 }
32 void insert(node n,node m)
33 {
34     node tt;
35     double tx = fabs(a * n.x + b * n.y + c);
36     double ty = fabs(a * m.x + b * m.y + c);
37     tt.x = (n.x * ty + m.x * tx) / (tx + ty);
38     tt.y = (n.y * ty + m.y * tx) / (tx + ty);
39     t[++tnum] = tt;
40 
41 }
42 void solve()
43 {
44     tnum = 0;
45     int i;
46     for(i = 1; i <= num; i++)
47     {
48         if(juge(a * tp[i].x + b * tp[i].y + c) >= 0)  //顺时针所以 >= 0
49         {
50             t[++tnum] = tp[i];
51         }
52         else
53         {
54             if(juge(a * tp[i - 1].x + b * tp[i - 1].y + c) > 0)
55             insert(tp[i - 1],tp[i]);
56             if(juge(a * tp[i + 1].x + b * tp[i + 1].y + c) > 0)
57             insert(tp[i + 1],tp[i]);
58         }
59     }
60 
61     for(i = 1; i <= tnum; i++)
62     tp[i] = t[i];
63     tp[0] = tp[tnum], tp[tnum + 1] = tp[1];
64     num = tnum;
65 }
66 int main()
67 {
68     int i,n;
69     int t;
70     //freopen("data.txt","r",stdin);
71     scanf("%d",&t);
72     while(t--)
73     //while(scanf("%d",&n), n)
74     {
75         scanf("%d",&n);
76         for(i = 0; i < n; i++)
77         {
78             scanf("%lf%lf",&p[i].x,&p[i].y);
79             tp[i + 1] = p[i];
80         }
81 
82         p[n] = p[0];
83         tp[0] = tp[n], tp[n + 1] = tp[1];
84         num = n;
85         for(i = 0; i < n; i++)
86         {
87             a = p[i + 1].y - p[i].y;
88             b = p[i].x - p[i + 1].x;
89             c = p[i + 1].x * p[i].y - p[i + 1].y * p[i].x;
90             solve();
91         }
92         if(!num) printf("NO\n");
93         else printf("YES\n");
94     }
95     return 0;
96 }