讨论 - AC者发题解！

Jollwish 2009-11-08 04:53:00

点我顶贴收藏删除

哪个AC了，发一下题解，20分奉上！

#1 Jollwish@2008-10-03 07:23:00

回复删除

捞起

#2 wish@2008-10-03 07:29:00

回复删除

只是一个思路，我也没写程序：

枚举连接这几个点的方式，判断是否成立

复杂度是 O(n!)

对于 n<=10 应该是可以通过的。。。

#3 chensqi@2009-04-18 20:43:00

回复删除

题目应该是说要形成一个封闭的环状图形....所以只有3种

#4 Jo11wish@2009-04-22 03:33:00

回复删除

UP...

#5 小小小学生@2009-04-24 21:48:00

回复删除

我也有思路。

就是找出把全部点连起来有多少个交叉点

然后总数减去一个数Y

当然这个数Y跟交叉点个数有着一一对应的关系。

至于这个关系了喔。。。。有待发现。。

#6 claire_@2009-09-29 16:17:00

回复删除

我的做法是从第一个点出发，进行深搜，判断是否与前面的线段相交，搜完一种方案，ans加1，最后把ans除以2(同一种可能是向左搜出来的，也可能向右）

#7 zxc2231603@2009-11-08 04:51:00

回复删除

var p:array[1..10,1..2]of longint；

l:array[1..10,1..10,1..3]of longint；

a:array[1..10,1..10,1..10,1..10]of boolean；

i1,i2,j1,j2,t,n:longint；

f:array[1..10]of boolean；

w:array[0..10]of longint；

procedure search(s:longint)；

var i,j:longint；

g:boolean；

begin

if s=n then

begin

inc(t)；

exit；

end；

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；

begin

assign(input,’lines.in’)；

reset(input)；

assign(output,’lines.out’)；

rewrite(output)；

repeat

inc(n)；

read(p[n,1],p[n,2])；

until (p[n,1]=0) and (p[n,2]=0)；

for i1:=1 to n do

for i2:=1 to n do

if i1<>i2 then

begin

l[i1,i2,1]:=p[i2,2]-p[i1,2]；

l[i1,i2,2]:=p[i1,1]-p[i2,1]；

l[i1,i2,3]:=p[i2,1]*p[i1,2]-p[i1,1]*p[i2,2]；

end；

for i1:=1 to n do

for i2:=1 to n do

if i1<>i2 then

for j1:=1 to n do

for j2:=1 to n do

if j1<>j2 then

begin

a[i1,i2,j1,j2]:=false；

if (l[j1,j2,1]*p[i1,1]+l[j1,j2,2]*p[i1,2]+l[j1,j2,3])*

(l[j1,j2,1]*p[i2,1]+l[j1,j2,2]*p[i2,2]+l[j1,j2,3])>0 then a[i1,i2,j1,j2]:=true；

if (l[i1,i2,1]*p[j1,1]+l[i1,i2,2]*p[j1,2]+l[i1,i2,3])*

(l[i1,i2,1]*p[j2,1]+l[i1,i2,2]*p[j2,2]+l[i1,i2,3])>0 then a[i1,i2,j1,j2]:=true；

end；

w[0]:=1；

f[1]:=true；

search(0)；

writeln(t div 2)；

close(input)；

close(output)；

end.

#8 donxinchen@2009-11-08 04:53:00

回复删除

program line；

var p:array[1..10,1..2]of longint；

l:array[1..10,1..10,1..3]of longint；

a:array[1..10,1..10,1..10,1..10]of boolean；

i1,i2,j1,j2,t,n:longint；

f:array[1..10]of boolean；

w:array[0..10]of longint；

procedure search(s:longint)；

var i,j:longint；

g:boolean；

begin

if s=n then

begin

inc(t)；

exit；

end；

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；

begin

assign(input,’lines.in’)；

reset(input)；

assign(output,’lines.out’)；

rewrite(output)；

repeat

inc(n)；

read(p[n,1],p[n,2])；

until (p[n,1]=0) and (p[n,2]=0)；

for i1:=1 to n do

for i2:=1 to n do

if i1<>i2 then

begin

l[i1,i2,1]:=p[i2,2]-p[i1,2]；

l[i1,i2,2]:=p[i1,1]-p[i2,1]；

l[i1,i2,3]:=p[i2,1]*p[i1,2]-p[i1,1]*p[i2,2]；

end；

for i1:=1 to n do

for i2:=1 to n do

if i1<>i2 then

for j1:=1 to n do

for j2:=1 to n do

if j1<>j2 then

begin

a[i1,i2,j1,j2]:=false；

if (l[j1,j2,1]*p[i1,1]+l[j1,j2,2]*p[i1,2]+l[j1,j2,3])*

(l[j1,j2,1]*p[i2,1]+l[j1,j2,2]*p[i2,2]+l[j1,j2,3])>0 then a[i1,i2,j1,j2]:=true；

if (l[i1,i2,1]*p[j1,1]+l[i1,i2,2]*p[j1,2]+l[i1,i2,3])*

(l[i1,i2,1]*p[j2,1]+l[i1,i2,2]*p[j2,2]+l[i1,i2,3])>0 then a[i1,i2,j1,j2]:=true；

end；

w[0]:=1；

f[1]:=true；

search(0)；

writeln(t div 2)；

close(input)；

close(output)；

end.