精华内容
下载资源
问答
  • 半平面交

    2018-12-11 08:40:09
    半平面交

    求多边形核POJ3335
    题意:一凸多边形球场,问是否在场上某处放一记分牌让所有边上观众看到

    
    #include <bits/stdc++.h>
    using namespace std;
    #define exp 1e-10
    struct node{double x;double y;};//定义点结构体
    node point[105];//记录最开始的多边形
    node q[105];    //临时保存新切割的多边形
    node p[105];    //保存新切割出的多边形
    int n,m;        //n原先点数,m新切出的多边形点数
    double a,b,c;   //切边系数
    void getline(node x,node y){//过XY两点获取直线ax+by+c==0系数
        a=y.y-x.y;
        b=x.x-y.x;
        c=y.x*x.y-x.x*y.y;
    }//本函数由数学列式化简可得
    node intersect(node x,node y){//获取交点:ax+by+c==0直线 和 点x和y所连直线
        double u=fabs(a*x.x+b*x.y+c);
        double v=fabs(a*y.x+b*y.y+c);
        node ans;
        ans.x=(x.x*v+y.x*u)/(u+v);
        ans.y=(x.y*v+y.y*u)/(u+v);
        return ans;
    }//本函数由数学列式化简可得
    void cut(){//用直线ax+by+c==0切割多边形,先用Q临时数组存本次切剩的边,最后再赋给P数组
        int cutm=0,i;//本轮切出的点初始化,I是循环系数而已
        for(i=1;i<=m;i++){//遍历一次全部点,每次取pi,pi-1,pi+1
            if(a*p[i].x+b*p[i].y+c>=0)q[++cutm]=p[i];
                    //题目是顺时钟给点,一个点在直线右边则带入值就会大于等于0
                    //在直线右边的意思就是这个点还在切割后的多边形内,将其保留
            else{   //该点不在多边形内
                if(a*p[i-1].x+b*p[i-1].y+c>0)q[++cutm]=intersect(p[i-1],p[i]);
                if(a*p[i+1].x+b*p[i+1].y+c>0)q[++cutm]=intersect(p[i+1],p[i]);
            }       //但是它和它相邻的点构成直线与ax+by+c==0所构成的交点可能在新切割出的多边形内
        }           //所以此时要保留
        for(i=1;i<=cutm;i++)p[i]=q[i];//把Q赋给P
        p[0]=q[cutm];   //末点记为第0个点
        p[cutm+1]=q[1]; //第一个点记到最后附加点
        m=cutm;         //更新切完后的新点数
    }//因为每次取出pi,pi-1,pi+1所以有上面的赋值
    void solve(){//求解
        for(int i=1;i<=n;i++)p[i]=point[i]; //复制
        p[n+1]=p[1];                        //把第一个点复制到第N+1个点
        p[0]=p[n];                          //把第N个点复制到第0个点
        m=n;                                //点数也初始复制
        for(int i=1;i<=n;i++){              //遍历
            getline(point[i],point[i+1]);   //根据point[i]和point[i+1]确定直线ax+by+c==0
            cut();                          //用直线ax+by+c==0切割多边形
        }
    }
    int main(){
        int cas;cin>>cas;//样例
        while(cas--){//样例自减
            scanf("%d",&n);//输入N
            for(int i=1;i<=n;i++)//遍历N个点,此题顺时针给出
                scanf("%lf%lf",&point[i].x,&point[i].y);//输入
            solve();//求解
            if(m==0)printf("NO\n");//切完的空间没有点就NO
            else printf("YES\n");//有就YES
        }
        return 0;
    }
    /*
    2
    4  0 0  0 1  1 1  1 0
    YES
    8  0 0  0 2  1 2  1 1  2 1  2 2  3 2  3 0
    NO
    */
    
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,912
精华内容 764
关键字:

半平面交