Lightning

题目：Lightning

总结：这道题先是根据点与点之间的距离，判断两个点是否相连。这个地方需要注意三点不能共线。假如这时有两个点可以将一个点与它们的斜率保存下来，然后只要别的点斜率不等于这个并且也没有这个点。那么就可以连通。然后构造基尔霍夫矩阵，然后再来求解行列式

#include <stdio.h>
#include <math.h>
#include <map>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 301;
const int mod = 10007;


struct str{
    double a,b,c,d;
}s[N<<5];
double x[N],y[N],r;
int a[N][N],c[N][N],n,fa[N];
int len;

double Dis(int i,int j){
    return sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
}
int det(int n){
    int ans = 1;
    for(int i = 1;i <= n;i++){
        for(int j = i+1;j <= n;j++){
            while(a[j][i]){
                int t = a[i][i]/a[j][i];
                for(int k = i;k <= n;k++) a[i][k] = ((a[i][k]-t*a[j][k])%mod+mod)%mod;
                swap(a[i],a[j]);
                ans = -ans;
            }
        }
        ans = (ans*a[i][i])%mod;
    }
    return (ans+mod)%mod;
}
bool check(int i,int j){
    double k = (y[j]-y[i])*1.0/(x[j]-x[i]);
    double b = y[j]-k*x[j];
    for(int t = 0;t < len;t++){
        if(s[t].a == x[i] && s[t].b == y[i] && k == s[t].c && b == s[t].d){
            return false;
        }
    }
    s[len].a = x[i];
    s[len].b = y[i];
    s[len].c = k;
    s[len++].d = b;
    return true;
}
void solve(){
    memset(a,0,sizeof a);
    memset(c,0,sizeof c);
    scanf("%d%lf",&n,&r);
    for(int i = 1;i <= n;i++){
        scanf("%lf%lf",x+i,y+i);
    }
    for(int i = 1;i <= n;i++){
        len = 0;
        for(int j = i+1;j <= n;j++){
            if(Dis(i,j) <= r && check(i,j)){
                a[i][i]++;
                a[j][j]++;
                c[i][j] = c[j][i] = 1;
            }
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            a[i][j] -= c[i][j];
         //   printf("%3d",c[i][j]);
        }
      //  printf("\n");
    }
    int ans = det(n-1);
    if(ans == 0) ans = -1;
    printf("%d\n",ans);
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--)
        solve();
    return 0;
}