HDU 4305 Contest 1

感觉是有很多细节要处理的。尤其是求逆元后的运算，应该是存在超范围的情况的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define MOD 10007
#define N 305
using namespace std;

struct point{
	int x,y;
}p[N];
int D[N][N],G[N][N],C[N][N];
bool vis[N];
int dist(point a,point b){
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

void getc(int n){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
		C[i][j]=D[i][j]-G[i][j];
	}
}

bool bfs(int n){
	int c=0;
	memset(vis,false,sizeof(vis));
	queue<int>que;
	que.push(1);
	vis[1]=true;
	while(!que.empty()){
		c++;
		int tmp=que.front();
		que.pop();
		for(int i=1;i<=n;i++){
			if(G[tmp][i]==1&&!vis[i]){
				que.push(i);
				vis[i]=true;
			}
		}
	}
	if(c==n) return true;
	else return false;
}

void exgcd (int a, int b, int &x, int &y)   
{   
    if (b == 0)   
    {   
        x = 1, y = 0;   
        return ;   
    }   
    exgcd (b, a%b, x, y);   
    int tp = x;   
    x = y;   
    y = tp - a/b*y;   
}	

int work(int n){
	int x,y;
	int sgn=0;
	for(int i=1;i<n;i++)
	for(int j=1;j<n;j++)
	C[i][j]=(C[i][j]%MOD+MOD)%MOD;
	for(int i=1;i<n;i++){
		if(C[i][i]==0){
			int j;
			for(j=i+1;j<n;j++)
			if(C[j][i]!=0)
			break;
			if(j>=n) return -1;
			for(int k=1;k<n;k++)
			swap(C[i][k],C[j][k]);
			sgn++;
		}
		exgcd(C[i][i],MOD,x,y);
		x=(x%MOD+MOD)%MOD;
		for(int j=i+1;j<n;j++){
			for(int k=i+1;k<n;k++){
				C[j][k]=((C[j][k]-(((C[i][k]*x)%MOD)*C[j][i])%MOD)%MOD+MOD)%MOD;
			}
		}
	}
	int ans=1;
	for(int i=1;i<n;i++)
	ans=(ans*(C[i][i]))%MOD;
	if(sgn&1)return (MOD-ans)%MOD;
	return ans;
}

int main(){
	int T,n,r;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&r);
		for(int i=1;i<=n;i++)
		scanf("%d%d",&p[i].x,&p[i].y);
		memset(D,0,sizeof(D));
		memset(G,0,sizeof(G));
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				if(i!=j){
					int tp=dist(p[i],p[j]);
					if(tp<=r*r){
						bool flag=true;
						for(int k=1;k<=n;k++){
							if(k!=i&&k!=j&&dist(p[i],p[k])<=dist(p[i],p[j])&&dist(p[j],p[k])<=tp
								&&(p[i].y-p[k].y)*(p[k].x-p[j].x)==(p[k].y-p[j].y)*(p[i].x-p[k].x)){
									flag=false;
									break;
							}
						}
						if(flag){
							D[i][i]++;D[j][j]++;
							G[i][j]=G[j][i]=1;
						}					
					}
				}
			}
		}
//		for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++)
//		cout<<D[i][j]<<' ';
//		cout<<endl;
//		}
		getc(n);
		if(!bfs(n)){
			printf("-1
");
		}
		else{
			int ans=work(n);
			printf("%d
",ans);
		}
	}
	return 0;
}