半平面交第一题 ！
题意是给出一个多边形，问他是否存在内核，即“可以看到任何一个地方的区域”。
内核即半平面交，下面是离线求半平面交的(nlogn)算法
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100;
struct Point{
double x,y;
Point(double xx=0,double yy=0){
x=xx,y=yy;
}
}a[maxn],p[maxn];
struct Vector{
double x,y;
Vector(double xx=0,double yy=0){
x=xx,y=yy;
}
};
struct Line{
Point p;
Vector v;
double ang;
Line(Point a=Point(),Vector b=Vector()){
p=a,v=b;
ang=atan2(b.y,b.x);
}
}b[maxn],q[maxn];
int dcmp(double x){return fabs(x)<1e-9?0:(x>0?1:-1);}
Vector operator - (Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}
Point operator + (Point a,Vector b){return Point(a.x+b.x,a.y+b.y);}
Vector operator * (double p,Vector a){return Vector(a.x*p,a.y*p);}
Vector operator * (Vector a,double p){return Vector(a.x*p,a.y*p);}
double operator * (Vector a,Vector b){return a.x*b.y-a.y*b.x;}
bool operator < (Line a,Line b){return a.ang<b.ang;}
bool onleft(Line a,Point b){return dcmp(a.v*(b-a.p))>0;}
Point glt(Point a,Point b,Point c,Point d){
Vector v1=b-a,v2=d-c,v3=a-c;
return a+v2*v3/(v1*v2)*v1;
}
int n,l,r;
void bpm(){
sort(b+1,b+n+1);
l=r=1;
q[1]=b[1]; //先加入第一条
for(int i=2;i<=n;i++){
while(l<r&&!onleft(b[i],p[r-1])) r--;
while(l<r&&!onleft(b[i],p[l])) l++; //如果不在左边就弹出去
q[++r]=b[i];
if(dcmp(b[i].v*q[r-1].v)==0){
r--;
if(onleft(q[r],b[i].p)) //这个应该是如果两个重合，就先把b[i]加入
q[r]=b[i];
}
if(l<r)
p[r-1]=glt(q[r-1].p,q[r-1].p+q[r-1].v,q[r].p,q[r].p+q[r].v); //交点更新
}
while(l<r&&!onleft(q[l],p[r-1])) r--; //有可能最后加入的几条是不合法的，要弹出来
}
int main(){
// freopen("3130.in","r",stdin);
while(1){
scanf("%d",&n);
if(n==0) break;
for(int i=1;i<=n;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
for(int i=1;i<n;i++)
b[i]=Line(a[i],a[i+1]-a[i]);
b[n]=Line(a[n],a[1]-a[n]);
bpm();
if(r-l<=1) printf("0
");
else printf("1
");
}
return 0;
}