题解

9 条题解

  • 1

    竟然没有题解,我来一发

    对于这种半平面交板子题,关键在于用自己交自己的思想,以及坑点(要输出两个\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的

  • 0
    @ 2009-08-12 17:46:33

    精度问题是关键!

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

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

  • 0
    @ 2009-04-27 21:49:58

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

    已删除

  • 0
    @ 2009-07-12 10:23:23

    Orz!!!现在AC了!!!

  • 0
    @ 2007-10-15 18:56:12

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

    纪念AC270题

    easy计算几何,2KB搞定

  • 0
    @ 2007-06-05 10:39:58

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

  • 0
    @ 2006-11-06 22:09:29

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

  • 0
    @ 2006-11-06 15:35:45

    我晕。。AC什么了啊?

  • 0
    @ 2006-11-06 14:09:23

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

  • 1

信息

ID
1296
难度
8
分类
计算几何 | 半平面交 点击显示
标签
(无)
递交数
161
已通过
24
通过率
15%
被复制
2
上传者