1 条题解
-
1
#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
- 上传者