http://poj.org/problem?id=3130
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 1000000
using namespace std; const double eps=(1e-);
struct point
{
double x,y;
};
double a,b,c;
int n,cutt=,m;
point p1[maxn];
point p2[maxn];
point p3[maxn]; void get(point c1,point c2)
{
a=c2.y-c1.y;
b=c1.x-c2.x;
c=c1.y*c2.x-c1.x*c2.y;
} point insertsect(point c1,point c2)
{
double u=fabs(a*c1.x+b*c1.y+c);
double v=fabs(a*c2.x+b*c2.y+c);
point p;
p.x=(c1.x*v+c2.x*u)/(u+v);
p.y=(c1.y*v+c2.y*u)/(u+v);
return p;
} void cut()
{
int cutnum=;
for(int i=; i<=m; i++)
{
if(a*p3[i].x+b*p3[i].y+c>=)
p2[++cutnum]=p3[i];
else
{
if(a*p3[i-].x+b*p3[i-].y+c>)
p2[++cutnum]=insertsect(p3[i-],p3[i]);
if(a*p3[i+].x+b*p3[i+].y+c>)
p2[++cutnum]=insertsect(p3[i+],p3[i]);
}
}
for(int i=; i<=cutnum; i++)
p3[i]=p2[i];
p3[cutnum+]=p2[]; p3[]=p2[cutnum];
m=cutnum;
} int main()
{
while(scanf("%d",&n)!=EOF)
{
if(n==) break;
for(int i=; i<=n; i++)
{
scanf("%lf%lf",&p1[i].x,&p1[i].y);
}
for(int i=; i<(n+)/; i++)
{
swap(p1[i],p1[n-i]);
}
for(int i=; i<=n; i++)
{
p3[i]=p1[i];
}
p1[n+]=p1[];
p3[n+]=p3[];
p3[]=p3[n];
m=n;
for(int i=; i<=n; i++)
{
get(p1[i],p1[i+]);
cut();
}
if(m==) printf("0\n");
else printf("1\n");
}
return ;
}