POJ1474：Video Surveillance—

http://poj.org/problem?id=1474

题目大意：给按照顺时针序的多边形顶点，问其是否有内核。

——————————————————————————————

（和上道题目一模一样，所以我把题解都照着搬过来了）

（绝对不是我偷懒……）

看了两个小时的资料，对板子敲了一个小时，终于将简单的板子题弄过了。

（原本计划去搞风水那道题，但发现我等级的太低了……需要从基础练起半平面交）

代码参考：http://blog.csdn.net/accry/article/details/6070621

理解参考：http://blog.csdn.net/acm_zl/article/details/11153475

（这个理解参考找了很久……我只看得懂这个，先看下面的再看上面的能对理解起到蛮好的帮助）

#include<cstdio>

#include<queue>

#include<cctype>

#include<cstring>

#include<stack>

#include<cmath>

#include<algorithm>

using namespace std;

typedef double dl;

const dl eps=1e-;

const int N=;

struct Point{

    dl x;

    dl y;

}p[N],point[N],q[N],z;

//point，初始点

//q，暂时存可行点

//p，记录可行点

int n,curcnt,cnt;

//curcnt，暂时存可行点个数

//cnt，记录可行点个数

inline Point getmag(Point a,Point b){

    Point s;

    s.x=b.x-a.x;s.y=b.y-a.y;

    return s;

}

inline dl multiX(Point a,Point b){

    return a.x*b.y-b.x*a.y;

}

inline void getline(Point x,Point y,dl &a,dl &b,dl &c){

    a=y.y-x.y;

    b=x.x-y.x;

    c=y.x*x.y-x.x*y.y;

    return;

}

inline Point intersect(Point x,Point y,dl a,dl b,dl c){

    Point s;

    dl u=fabs(a*x.x+b*x.y+c);

    dl v=fabs(a*y.x+b*y.y+c);

    s.x=(x.x*v+y.x*u)/(u+v);

    s.y=(x.y*v+y.y*u)/(u+v);

    return s;

}

inline void cut(dl a,dl b,dl c){

    curcnt=;

    for(int i=;i<=cnt;i++){

        if(a*p[i].x+b*p[i].y+c>-eps)q[++curcnt]=p[i];

        else{

            if(a*p[i-].x+b*p[i-].y+c>eps){

                q[++curcnt]=intersect(p[i],p[i-],a,b,c);

        }

            if(a*p[i+].x+b*p[i+].y+c>eps){

                q[++curcnt]=intersect(p[i],p[i+],a,b,c);

        }

        }

    }

    for(int i=;i<=curcnt;i++)p[i]=q[i];

    p[curcnt+]=p[];p[]=p[curcnt];

    cnt=curcnt;

    return;

}

inline void init(){

    for(int i=;i<=n;i++)p[i]=point[i];

    z.x=z.y=;

    p[n+]=p[];

    p[]=p[n];

    point[n+]=point[];

    cnt=n;

    return;

}

inline void regular(){//调换方向

    for(int i=;i<(n+)/;i++)swap(point[i],point[n-i]);

    return;

}

inline bool solve(){

    //注意：默认点是顺时针，如果题目不是顺时针，规整化方向

    init();

    for(int i=;i<=n;i++){

        dl a,b,c;

        getline(point[i],point[i+],a,b,c);

        cut(a,b,c);

    }

    return cnt;

}

int main(){

    int cntt=;

    while(scanf("%d",&n)!=EOF&&n){

        for(int i=;i<=n;i++){

            scanf("%lf%lf",&point[i].x,&point[i].y);

        }

    printf("Floor #%d\n",++cntt);

        if(!solve())puts("Surveillance is impossible.");

        else puts("Surveillance is possible.");

    putchar('\n');

    }

    return ;

}

巴特西

POJ1474：Video Surveillance——题解

最新文章

热门文章