讨论 / PID281点和线为什么我的程序WA 0
drcool 2014-01-09 06:29:18
点我顶贴 收藏 删除
AC的程序有点看不懂:

这是在干什么?

for i:=1 to n do

if (not f[i]) or (s=n-1) then

begin

g:=true;

for j:=1 to s-1 do

if (s<>n-1) or (j<>1) then if not a[w[s],i,w[j-1],w[j]] then g:=false;

if g then

begin

f[i]:=true;

w[s+1]:=i;

search(s+1);

f[i]:=false;

end;

end;

//我的程序如下,就是从每个点出发深搜,同时满足和前面的线不相交,最后把结果除2,但是一个点都不过,请帮忙查找错误。或者发C/C++的AC程序也行

#include <stdio.h>

#include <string.h>

struct point { int x, y; };

int min(int a, int b) { return a < b ? a : b; }

int max(int a, int b) { return a > b ? a : b; }

bool inter(point a, point b, point c, point d){

if ( min(a.x, b.x) > max(c.x, d.x) ||

min(a.y, b.y) > max(c.y, d.y) ||

min(c.x, d.x) > max(a.x, b.x) ||

min(c.y, d.y) > max(a.y, b.y) ) return 0;

int h, i, j, k;

h = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);

i = (b.x - a.x) * (d.y - a.y) - (b.y - a.y) * (d.x - a.x);

j = (d.x - c.x) * (a.y - c.y) - (d.y - c.y) * (a.x - c.x);

k = (d.x - c.x) * (b.y - c.y) - (d.y - c.y) * (b.x - c.x);

return h * i <0 && j * k <0;

}

point A[11];

int n;

int line[50][2];

int XX[50][50];

int pp[10][10];

char d[10];

char v[10];

int ans;

void dfs(int from , int deep)

{

int i,j,k,s;

v[from]=1;

d[deep]=from;

for(i=0;i<n;i++)

{

if(!v[i])

{

k=pp[from][i];

for(j=0;j<deep;j++)

{

s=pp[d[j]][d[j+1]];

if(XX[k][s]) break;

}

if(j==deep)

dfs(i,deep+1);

}

}

if(deep==n-1)

ans++;

v[from]=0;

}

int main()

{

int i,j,k=0;

while(1)

{

scanf("%d%d",&A[n].x,&A[n].y);

if(!A[n].x&&!A[n].y) break;

n++;

}

for(i=0;i<n;i++)

{

for(j=i+1;j<n;j++)

{

line[k][0]=i;

line[k][1]=j;

pp[i][j]=pp[j][i]=k;

k++;

}

}

for(i=0;i<k;i++)

{

for(j=i+1;j<k;j++)

{

if((line[i][0]==line[j][0])||(line[i][0]==line[j][1])||(line[i][1]==line[j][0])||(line[i][1]==line[j][1])) continue;

if(inter(A[line[i][0]], A[line[i][1]], A[line[j][0]], A[line[j][1]]))

XX[i][j]=XX[j][i]=1;

}

}

for(i=0;i<n;i++)

{

dfs(i,0);

}

printf("%d",ans/2);

return 0;

}

#1 drcool@2014-01-09 08:40:22
回复 删除
明白了,原来是连成圈
#2 drcool@2014-01-10 01:40:13
回复 删除
坑爹啊,不仅要连成圈,而且最后的0,0也要算在内!!
查看更多回复
提交回复