竟然没有题解，我来一发

对于这种半平面交板子题，关键在于用自己交自己的思想，以及坑点（要输出两个\n）还有就是第38行要把n记下来，因为会改变。

我是 O(n^2)算法

更多的见代码：

#include<stdio.h>
#include<string.h>
#define maxn 100000
struct point{double x,y;
}a[maxn],b[maxn],tmp[maxn];
int N,n;
double Cross(point A,point B,point C)
{
    return (A.x-C.x)*(B.y-C.y)-(B.x-C.x)*(A.y-C.y);
}
double fabs(double x)
{
    return x<0?-x:x;
}
void AddCross(point A,point B,point C,point D)
{
    double c1=fabs(Cross(D,B,A)),c2=fabs(Cross(C,B,A));
    b[++N].x=(c1*C.x+c2*D.x)/(c1+c2),b[N].y=(c1*C.y+c2*D.y)/(c1+c2);
}
void Cut(point A,point B)
{
    N=0,a[n+1]=a[1];
    for(int i=1;i<=n;i++)
        if(Cross(a[i],B,A)>=0)
        {
            b[++N]=a[i];
            if(Cross(a[i+1],B,A)<0) AddCross(A,B,a[i],a[i+1]);
        }
        else if(Cross(a[i+1],B,A)>0) AddCross(A,B,a[i],a[i+1]);
    for(int i=1;i<=N;i++) a[i]=b[i];
    n=N;
}
int main()
{
    int T=0;
    while(scanf("%d",&n)&&n)
    {
        int m=n;
        for(int i=1;i<=n;i++) scanf("%lf %lf",&a[i].x,&a[i].y),tmp[i]=a[i];
        for(int i=1;i<m;i++) Cut(tmp[i],tmp[i+1]);
        ++T;
        Cut(tmp[m],tmp[1]);
        if(n) printf("Room #%d:\nSurveillance is possible.\n\n",T);
        else printf("Room #%d:\nSurveillance is impossible.\n\n",T);
    }
    return 0;
}

可以不开double的

精度问题是关键！

第7个点WA了好几次。不能直接和0比较，要1e-6！

此题数据规模小，N^3的裸算法也能秒杀。只要65行。

原数据有两个点精度上有点问题

已删除

Orz！！！现在AC了！！！

第6个AC的，此题通过率+2%

纪念AC270题

easy计算几何，2KB搞定

就五字:星形多边形`暂时不想做\`

貌似数据有问题.........

我晕。。AC什么了啊？

你厉害。。。通过人数为0然后你AC