题目大意：
分析：
所以题目的关键变为寻找平行的右邻接点
N的数目较小，，对所有的情况进行列举即可。
/*ID: abc18711LANG: CTASK: wormhole*/#include <stdio.h>#include <string.h>#define MAXN 12+1int X[MAXN];int Y[MAXN];int pair[MAXN];int right_hole[MAXN];int N;int exist_cycle(){int start_hole;int flag;int i;for (start_hole=1; start_hole<=N; start_hole++){for (i=1,flag=start_hole; i<=N; i++){flag = right_hole[ pair[flag] ];if(flag == 0) break;}if (flag > 0) return 1;}return 0;}// the pair combinationint solutions(){int i;int j;int total = 0;//find first unpaired holefor (i=1; i<=N; i++)if(pair[i] == 0) break;//no unpaired hole,test the cycleif (i > N){return exist_cycle();}//pairing i and jfor (j=i+1; j<=N; j++)if (pair[j] == 0){pair[i] = j;pair[j] = i;total += solutions();pair[i] = pair[j] = 0;}return total;}int main(){int i;int j;FILE *fin = fopen("wormhole.in", "r");FILE *fout = fopen("wormhole.out", "w");// get the input fscanf(fin, "%d", &N);for (i=1; i<=N; i++)fscanf(fin, "%d %d", &X[i], &Y[i]);memset(pair, 0, MAXN*sizeof(int));memset(right_hole, 0, MAXN*sizeof(int));// find the right holefor( i=1; i<=N; i++)for (j=1; j<=N; j++)if (Y[i] == Y[j] && X[j] > X[i])if (right_hole[i] == 0 || (X[j]-X[i]) < (X[ right_hole[i] ]-X[i]))right_hole[i] = j;fprintf(fout, "%d\n", solutions());return 0;}
附录：
Wormholes
FarmerJohn’shobbyofconductinghigh-energyphysicsexperimentsonweekendshasbackfired,causingNwormholes(2<=N<=12,Neven)tomaterializeonhisfarm,eachlocatedatadistinctpoint
onthe2Dmapofhisfarm(thex,ycoordinatesarebothintegers).
Accordingtohiscalculations,FarmerJohnknowsthathiswormholeswillformN/2connectedpairs.Forexample,ifwormholesAandBareconnectedasapair,then
anyobjectenteringwormholeAwillexitwormholeBmovinginthesamedirection,andanyobjectenteringwormholeBwillsimilarlyexitfromwormholeAmovingin
thesamedirection.Thiscanhaveratherunpleasantconsequences.
Forexample,supposetherearetwopairedwormholesAat(1,1)andBat(3,1),andthatBessiethecowstartsfromposition(2,1)movinginthe+xdirection.Bessiewill
enterwormholeB[at(3,1)],exitfromA[at(1,1)],thenenterBagain,andsoon,gettingtrappedinaninfinitecycle!
|….|A>B.BessiewilltraveltoBthen+….AthenacrosstoBagain
FarmerJohnknowstheexactlocationofeachwormholeonhisfarm.HeknowsthatBessiethecowalwayswalksinthe+xdirection,althoughhedoesnotremember
whereBessieiscurrentlylocated.
PleasehelpFarmerJohncountthenumberofdistinctpairingsofthewormholessuchthatBessiecouldpossiblygettrappedinaninfinitecycleifshestartsfroman
unluckyposition.FJdoesn’tknowwhichwormholepairswithanyotherwormhole,sofindallthepossibilities.
PROGRAMNAME:wormholeINPUTFORMAT:
Line1:
Thenumberofwormholes,N.
Lines2..1+N:
Eachlinecontainstwospace-separatedintegersdescribingthe(x,y)coordinatesofasinglewormhole.
Eachcoordinateisintherange0..1,000,000,000.
SAMPLEINPUT(filewormhole.in):
4
00
10
11
01
INPUTDETAILS:
Thereare4wormholes,formingthecornersofasquare.
OUTPUTFORMAT:
Line1:
ThenumberofdistinctpairingsofwormholessuchthatBessiecouldconceivablygetstuckin
acyclewalkingfromsomestartingpointinthe+xdirection.
SAMPLEOUTPUT(filewormhole.out):
2
OUTPUTDETAILS:放手后的微笑，只是用来掩盖疼痛的伤疤…
