坑爹点②:最后所有点要连成一个圈,但是按照题意不连成圈也可以把所有点连起来,这就比较蛋疼了。
就是上面这两点让我浪费了好长的时间,以后希望网站管理者把这种题意不明或者评测数据不对的清理掉,太坑了
#include <cstdio>
#include <cstring>
using namespace std;
struct point{
double x,y;
};
int n=0,ans[15],sum=0,flag[15]={0};
point a[15];
double f(point p0,point p1,point p2){
return ((p2.x-p0.x)*(p1.y-p0.y)-(p2.y-p0.y)*(p1.x-p0.x));}
int isjiao(point p1,point p2,point p3,point p4){//判断p1p2与p3p4是否相交
double d1,d2,d3,d4;
d1=f(p1,p2,p3);
d2=f(p1,p2,p4);
d3=f(p3,p4,p1);
d4=f(p3,p4,p2);
return (d1*d2<0)&&(d3*d4<0);}
int check(int k,int m){//检查ans[k]=m是否可以
int i;
for(i=1;i<=k-2;i++)
if(isjiao(a[ans[i]],a[ans[i+1]],a[ans[k-1]],a[m])) return 0;
return 1;}
void dfs(int k){
int i;
if(k>n){
if(check(k,1)) sum++;
return;}
for(i=2;i<=n;i++)
if(!flag[i]&&check(k,i)){
flag[i]=1;ans[k]=i;dfs(k+1);
flag[i]=0;}}
int main(){
int i;
double x,y;
while(1){
scanf("%lf%lf",&x,&y);
n++;a[n].x=x;a[n].y=y;
if(x==0&&y==0) break;}
flag[1]=1;ans[1]=1;dfs(2);
printf("%d",sum/2);
return 0;}