POJ_3130
对于半平面交的一些简明扼要的介绍可以参考这篇博客：http://blog.csdn.net/accry/article/details/6070621。此外，这篇博客上介绍的还有我敲出的程序都只是比较好理解的O(n^2)的求半平面交的算法，对于O(nlogn)的算法可以参考朱泽园的论文。
由于这个题目指明了多边形上的点是按逆时针序给出的，因而就不用再将每组数据都其统一成某个顺序了。
#include<stdio.h>
#include<string.h>
#define MAXD 110
#define zero 1e-8
#define INF 100000
struct point
{
double x, y;
}p[MAXD], wa[MAXD], wb[MAXD], *a, *b;
int N, an, bn;
double fabs(double x)
{
return x < 0 ? -x : x;
}
int dcmp(double x)
{
return fabs(x) < zero ? 0 : (x < 0 ? -1 : 1);
}
double det(double x1, double y1, double x2, double y2)
{
return x1 * y2 - x2 * y1;
}
void init()
{
int i, j, k;
for(i = 0; i < N; i ++)
scanf("%lf%lf", &p[i].x, &p[i].y);
p[N] = p[0];
}
void add(double x, double y)
{
b[bn].x = x, b[bn].y = y;
++ bn;
}
void cut(int k)
{
int i, j, tn;
point *t;
double x, y, t1, t2;
bn = 0;
for(i = 0; i < an; i ++)
{
t1 = det(p[k + 1].x - p[k].x, p[k + 1].y - p[k].y, a[i].x - p[k].x, a[i].y - p[k].y);
t2 = det(p[k + 1].x - p[k].x, p[k + 1].y - p[k].y, a[i + 1].x - p[k].x, a[i + 1].y - p[k].y);
if(dcmp(t1) >= 0)
add(a[i].x, a[i].y);
if(dcmp(t1) * dcmp(t2) < 0)
{
x = (fabs(t2) * a[i].x + fabs(t1) * a[i + 1].x) / (fabs(t1) + fabs(t2));
y = (fabs(t2) * a[i].y + fabs(t1) * a[i + 1].y) / (fabs(t1) + fabs(t2));
add(x, y);
}
}
t = a, a = b, b = t;
tn = an, an = bn, bn = tn;
a[an] = a[0];
}
void solve()
{
int i, j, k;
a = wa, b = wb;
an = 4;
a[0].x = -INF, a[0].y = -INF, a[1].x = INF, a[1].y = -INF, a[2].x = INF, a[2].y = INF, a[3].x = -INF, a[3].y = INF;
a[4] = a[0];
for(i = 0; i < N; i ++)
cut(i);
if(an == 0)
printf("0\n");
else
printf("1\n");
}
int main()
{
for(;;)
{
scanf("%d", &N);
if(!N)
break;
init();
solve();
}
return 0;
}