记录编号	84509	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO DEC13]虫洞	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.044 s
提交时间	2013-12-14 15:55:33	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int SIZEN=13;
const ll INF=1111111111*9;
ll px[SIZEN]={0},py[SIZEN]={0};
int next[SIZEN]={0};
int match[SIZEN]={0,3,4,1,2,7,8,5,6,11,12,9,10};
bool flag[SIZEN]={0};
int N;
int ans=0;
bool go(int x){//从第x个洞出来,若陷入循环就是true
	bool vis[SIZEN]={0};
	while(vis[x]==false){
		if(next[x]==0) return false;
		vis[x]=true;
		x=next[x];
		x=match[x];
	}
	return true;
}
bool check(void){
	int i;
	for(i=1;i<=N;i++) if(go(i)) return true;
	return false;
}
void DFS(int x){
	if(x==N/2){
		if(check()) ans++;
	}
	int i=x+1,j;
	while(flag[i]) i++;
	for(j=i+1;j<=N;j++){
		if(flag[j]) continue;
		flag[i]=flag[j]=true;
		match[i]=j,match[j]=i;
		DFS(x+1);
		flag[i]=flag[j]=false;
	}
}
void init(void){
	scanf("%d",&N);
	int i,j;
	ll temp;
	for(i=1;i<=N;i++) scanf("%lld%lld",&px[i],&py[i]);
	for(i=1;i<=N;i++){
		temp=INF;
		for(j=1;j<=N;j++){
			if(j==i) continue;
			if(py[i]==py[j]&&px[i]<=px[j]&&px[j]-px[i]<temp){
				temp=px[j]-px[i];
				next[i]=j;
			}
		}
	}
}
int main(){
	freopen("wormhole.in","r",stdin);
	freopen("wormhole.out","w",stdout);
	init();
	DFS(0);
	cout<<ans<<endl;
	return 0;
}