题解 P5696 【[CTSC1998]监视摄像机】

KaisuoShutong · 2019-12-06 20:05:30 · 题解

竟然没有题解，我来一发

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

我是 O(n^2) 算法，更快的 O(n\space logn) 请出门左转；

更多的见代码：

#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的 QwQ