【半平面交】POJ - 3335 - Rotating Scoreboard

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

---

题意

给出一个多边形，问多边形内是否存在一个点，使得多边形每个角上的点都有一条不穿过多边形边的直线与其相连。

---

题解

半平面交模板题，算法实现步骤：

1. 按逆时针连边
2. 以原点为中心，按极角坐标排序
3. 去重，对于同一个极角的直线选取在左边的一条
4. 一条条加入直线，在双端队列两端在外部的直线排除
5. 最后对双端队列首尾加入的直线判断一下

---

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=207;
const db eps=1e-7;
int sign(db k){if(k>eps) return 1;if(k<-eps) return -1; return 0;}
int dcmp(db k1,db k2){return sign(k1-k2);}
struct point{
    db x,y;
    point operator - (const point k)const{
        return (point){x-k.x,y-k.y};
    }
    point operator + (const point k)const{
        return (point){x+k.x,y+k.y};
    }
    point operator * (const db k)const{
        return (point){x*k,y*k};
    }
    point operator / (const db k)const{
        return (point){x/k,y/k};
    }
    db angle(){return atan2(y,x);}
    void print(){printf("(%f,%f)\n",x,y);}
}P[N];
db cross(point k1,point k2){
    return k1.x*k2.y-k1.y*k2.x;
}
db dot(point k1,point k2){
    return k1.x*k2.x+k1.y*k2.y;
}
struct line{
    point s,e;
    db angle(){return (e-s).angle();}
}L[N],dq[N];
point getLL(line k1,line k2){
    db w1=cross(k1.s-k2.s,k2.e-k2.s),w2=cross(k2.e-k2.s,k1.e-k2.s);
    return (k1.s*w2+k1.e*w1)/(w1+w2);
}
bool onRight(line k,point p){
    return sign((cross(p-k.s,k.e-k.s)))>0;
}
bool cmp(line k1,line k2){
    if(dcmp(k1.angle(),k2.angle())==0) return onRight(k2,k1.s);
    return k1.angle()<k2.angle();
}
int n,tot;
bool halfplaneinsert(){
    sort(L+1,L+1+tot,cmp);
    int cnt=0;
    for(int i=1;i<=tot;i++){
        if(i<tot&&dcmp(L[i].angle(),L[i+1].angle())==0) continue;
        L[++cnt]=L[i];
    }
    int tail=-1,head=0;
    for(int i=1;i<=cnt;i++){
        while(tail-head>=1&&onRight(L[i],getLL(dq[tail],dq[tail-1]))) tail--;
        while(tail-head>=1&&onRight(L[i],getLL(dq[head],dq[head+1]))) head++;
        dq[++tail]=L[i];
    }
    while(tail-head>=1&&onRight(dq[head],getLL(dq[tail],dq[tail-1]))) tail--;
    while(tail-head>=1&&onRight(dq[tail],getLL(dq[head],dq[head+1]))) head++;
    return tail-head>=2;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lf%lf",&P[i].x,&P[i].y);
        }
        tot=0;
        for(int i=n;i>1;i--){
            L[++tot]=(line){P[i],P[i-1]};
        }
        L[++tot]=(line){P[1],P[n]};
        if(halfplaneinsert()) printf("YES\n");
        else printf("NO\n");
    }
}