讨论 / 这题非常坑爹,做之前看过来
沧海一声喵 2018-01-27 05:02:00
点我顶贴 收藏 删除
坑爹点①:其实(0,0)点是要算进去的,但是题目中说不算进去,所以题目中的样例实际上是四个点(就说坑不坑)。

坑爹点②:最后所有点要连成一个圈,但是按照题意不连成圈也可以把所有点连起来,这就比较蛋疼了。

就是上面这两点让我浪费了好长的时间,以后希望网站管理者把这种题意不明或者评测数据不对的清理掉,太坑了

#1 沧海一声喵@2018-01-27 05:02:38
回复 删除
最后附上c++的AC代码

#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;}

查看更多回复
提交回复