1 条题解

  • 1
    @ 2022-7-16 21:49:53
    #include<bits/stdc++.h>
    using namespace std;
    struct point
    {
    	double X,Y;
    }a[15];
    int p[15],n,ans;//p为选择的下标
    bool cho[15];//cho表示是否已经选择
    inline double cross(point x,point y)//叉积,这里向量也用point表示了,懒得开一个新的struct
    {
    	return x.X*y.Y-x.Y*y.X;
    }
    inline bool intersection(point x1,point y1,point x2,point y2)//判断是否有交点,有交点返回true
    {
    	double abc=cross((point){y1.X-x1.X,y1.Y-x1.Y},(point){x2.X-x1.X,x2.Y-x1.Y});
    	double abd=cross((point){y1.X-x1.X,y1.Y-x1.Y},(point){y2.X-x1.X,y2.Y-x1.Y});
    	if((abc>0&&abd>0)||(abc<0&&abd<0))
    		return false;
    	swap(x1,x2);
    	swap(y1,y2);
    	abc=cross((point){y1.X-x1.X,y1.Y-x1.Y},(point){x2.X-x1.X,x2.Y-x1.Y});
    	abd=cross((point){y1.X-x1.X,y1.Y-x1.Y},(point){y2.X-x1.X,y2.Y-x1.Y});
    	return ((abc>0&&abd<0)||(abc<0&&abd>0));
    }
    void dfs(int d)
    {
    	if(d>n)
    	{
    		int i;
    		for(i=2;i<n-1;i++)
    			if(intersection(a[p[n]],a[p[1]],a[p[i]],a[p[i+1]]))
    				break;//第一个与最后一个连成的线段与其他是否有交点也要判断
    		if(i==n-1)
    			ans++;
    		return;
    	}
    	for(int i=1;i<=n;i++)
    		if(!cho[i])
    		{
    			int j;
    			p[d]=i;
    			for(j=1;j<d-2;j++)
    				if(intersection(a[p[d-1]],a[p[d]],a[p[j]],a[p[j+1]]))
    					break;
    			if(j>=d-2)
    			{
    				cho[i]=true;
    				dfs(d+1);
    				cho[i]=false;
    			}
    		}
    }
    int main()
    {
    	do
    	{
    		n++;
    		cin>>a[n].X>>a[n].Y;
    	}while(a[n].X!=0||a[n].Y!=0);
    	dfs(1);
    	cout<<ans/n/2;//一个多边形按照顺时针顺序有n个排列表示,逆时针也有n个,所以要除以2n
    	return 0;
    }
    
    • 1

    信息

    ID
    154
    时间
    1000ms
    内存
    125MiB
    难度
    5
    标签
    递交数
    3
    已通过
    2
    上传者