【CTSC1998】监视摄像机 | Mrsrz's blog

多边形的核，半平面交

题目大意：

给定一个多边形，问其内部是否存在一个点，其与多边形内部、边、点的连线上不存在另一条边。

题解：

就是要判断多边形内部是否存在核。

不难发现，对每个点，能看到这个点及其夹边的所有点构成的区域，恰是两条夹边的半平面的交。

那我们对每个点，都有这么一部分半平面，这些半平面的交的部分，就是合法区域。

我们只要求这些多边形的边是否存在半平面交即可。

观察数据较小，可以使用一些比较暴力的算法。

一个大小有限的半平面交，显然是一个凸包，这些凸包上的点一定是半平面的直线的交点。

我们把这些所有交点拿出来，然后对每个交点，如果它在半平面交内部，则所有半平面都包含它。枚举半平面，叉积判断其是否在半平面内部即可。

最后检查是否有点在半平面内部即可。

时间复杂度 $O(n^3)$。足以承受本题的数据范围。

Code：

#include<cstdio>
#include<vector>
using namespace std;
const int N=105;
int n;
template<typename T>
struct point{
    T x,y;
    inline point operator-(const point&r)const{return(point){x-r.x,y-r.y};}
};
point<int>d[N];
template<typename T>
inline T cross(const point<T>&a,const point<T>&b){return a.x*b.y-a.y*b.x;}
inline int Next(int x){return(x%n+1);}
vector<point<double> >vec;
bool vis[N*N*5];
point<double>get(point<int>a1,point<int>a2,point<int>b1,point<int>b2){
    if(a1.x==a2.x&&b1.x==b2.x)return(point<double>){23333,23333};
    double k_a=(a2.y-a1.y)*1./(a2.x-a1.x),k_b=(b2.y-b1.y)*1./(b2.x-b1.x);
    double b_a=a1.y-k_a*a1.x,b_b=b1.y-k_b*b1.x;
    if(a1.x==a2.x)return(point<double>){a1.x,a1.x*k_b+b_b};
    if(b1.x==b2.x)return(point<double>){b1.x,b1.x*k_a+b_a};
    double x=(b_b-b_a)/(k_a-k_b);
    return(point<double>){x,x*k_a+b_a};
}
int main(){
    int T=0;
    while(scanf("%d",&n),n){
        vec.clear();
        for(int i=n;i;--i)
            scanf("%d%d",&d[i].x,&d[i].y);
        for(int i=1;i<=n;++i){
            int j=Next(i);
            for(int k=j;Next(k)!=i;k=Next(k)){
                point<double>s=get(d[i],d[j],d[k],d[Next(k)]);
                if(s.x*s.y<1e9)
                vec.push_back(s);
            }
        }
        for(int i=0;i<vec.size();++i)vis[i]=1;
        for(int i=1;i<=n;++i){
            int j=Next(i);
            for(int id=0;id<vec.size();++id)if(vis[id]){
                point<double>a=(point<double>){d[j].x-d[i].x,d[j].y-d[i].y};
                point<double>b=(point<double>){vec[id].x-d[i].x,vec[id].y-d[i].y};
                double cr=a.x*b.y-a.y*b.x;
                if(cr+1e-9<0)vis[id]=0;
            }
        }
        bool ok=0;
        for(int i=0;i<vec.size()&&!ok;++i)ok=vis[i];
        printf("Room #%d:\nSurveillance is %spossible.\n\n",++T,(ok)?"":"im");
    }
    return 0;
}