poj 3130 How I Mathematician Wonder What You Are!

半平面交的一个题,也是求多边形的核心。求出这个好像也可以用于解决一些线性规划问题。我用的是N * N的基本算法,每加入一条直线,就对原来求出的半平面交进行处理,产生新的核心。
代码参照台湾的一个网站演算法笔记上的内容和代码。表示这个网站巨不错,求凸包的算法也参照了这个网站上的内容和代码。半平面交的地址:http://www.csie.ntnu.edu.tw/~u91029/Half-planeIntersection.html#a4

代码思路主要是:先读入所有的多边形顶点,放入一个vector(vp)里面,然后对多边形的每条边求一个半平面。刚开始的时候,用一个vector(Polygon)保存代表上下左右四个无限远角的四个点,表示原始的半平面。然后,用读入的多边形的每条边去切割原来的半平面。
切割的过程是,如果原来(Polygon)中的点在当前直线的指定一侧,那么原来的点还是有效的。如果原来的点和它相邻的下一个点与当前直线相交,那么还需要把交点加入Polygon集合。
还有求交点的方法比较奇葩,类似于黑书上面的那种根据面积等分的方法。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

double fPre = 1e-8;
struct Point
{
double x;
double y;
Point() {}
Point(double fX, double fY)
{
x = fX, y = fY;
}
};
typedef vector<Point> Polygon;
typedef pair<Point, Point> Line;
Point operator+(const Point a, const Point b)
{
Point t;
t.x = a.x + b.x;
t.y = a.y + b.y;
return t;
}

Point operator-(const Point a, const Point b)
{
Point t;
t.x = a.x - b.x;
t.y = a.y - b.y;
return t;
}

Point operator*(Point a, double fD)
{
Point t;
t.x = a.x * fD;
t.y = a.y * fD;
return t;
}

int DblCmp(double fD)
{
return fabs(fD) < fPre ? 0 : (fD > 0 ? 1 : -1);
}

double Det(double fX1, double fY1, double fX2, double fY2)
{
return fX1 * fY2 - fX2 * fY1;
}
//3点叉积
double Cross(Point a, Point b, Point c)
{
return Det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}
//向量叉积
double Cross(Point a, Point b)
{
return a.x * b.y - a.y * b.x;
}

//求直线交点的一种简便方法
//平行四边形面积的比例等于高的比例
Point Intersection(Point a1, Point a2, Point b1, Point b2)
{
Point a = a2 - a1;
Point b = b2 - b1;
Point s = b1 - a1;

return a1 + a * (Cross(b, s) / Cross(b, a));
}

Polygon HalfPlane(Polygon pg, Point a, Point b)
{
Polygon pgTmp;
int nN = pg.size();
for (int i = 0; i < nN; ++i)
{
double fC = Cross(a, b, pg[i]);
double fD = Cross(a, b, pg[(i + 1) % nN]);
if (DblCmp(fC) >= 0)
{
pgTmp.push_back(pg[i]);
}
if (fC * fD < 0)
{
pgTmp.push_back(Intersection(a, b, pg[i], pg[(i + 1) % nN]));
}
}
return pgTmp;
}

int main()
{
int nN;
Point p;
vector<Point> vp;
Polygon pg;

while (scanf("%d", &nN), nN)
{
vp.clear();
for (int i = 0; i < nN; ++i)
{
scanf("%lf%lf", &p.x, &p.y);
vp.push_back(p);
}
pg.clear();
pg.push_back(Point(-1e9, 1e9));
pg.push_back(Point(-1e9, -1e9));
pg.push_back(Point(1e9, -1e9));
pg.push_back(Point(1e9, 1e9));
for (int i = 0; i < nN; ++i)
{
pg = HalfPlane(pg, vp[i], vp[(i + 1) % nN]);
if (pg.size() == 0)
{
printf("0\n");
break;
}
}
if (pg.size())
{
printf("1\n");
}
}

return 0;
}