题意：给出n个人和他们的坐标，闪电随机劈到一个机器人，在他周围的与他距离不超过r的机器人会被传播，但是三点共线的情况只能传染最近的那个，传染后的有多少种情况。
也就是无相连通图的生成树的个数。
对于一个无向连通图来说，它可能有很多生成树，那么如何求得它的生成树个数呢？
首先给出一个非常一般的计算方法 -- 矩阵行列式法
对于任何一个顶点数为n的无向连通图，我们列出一个矩阵。
矩阵的规则是：
1、在主对角线上的元素为此节点的度数
2、对于其他位置上的元素Matrix(i,j) { i != j }，
(1) 如果节点i和节点j连通，则Matrix(i,j)的值为-k，其中k值为节点i到节点j的平行边个数。如果此图是一个简单图，即任意两点间不存在平行边，那么这个值就为-1.
(2) 但如果节点i和节点j根本不连通，则Matrix(i,j)的值为0。
这样的一个矩阵Matrix就会很容易的用O(n^2)的复杂度建立。接下来如何求得这个无向连通图的生成树个数呢。
直接给出定理：
撤去任意一个节点的信息，求出剩下的(n-1)*(n-1)矩阵的行列式，此值即为这个无向连通图的生成树个数。复杂度为O(n^3)
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 305
int a[maxn][maxn],x[maxn],MOD;
int map[maxn][maxn];
int gauss(int r, int c)
{
bool flag=false;
int coe=1;
int i=0,t=0;
for(int j=0; j<c; ++j)
{
int index=i;
for(int k=i; k<r; ++k)
if(a[k][j]>0)
{
index=k;
break;
}
if(a[index][j])
{
if(index != i)
{
for(int k=j; k<c; ++k)
swap(a[i][k],a[index][k]);
flag = !flag;
}
for(int k=i+1; k<r; ++k)
if(a[k][j])
{
coe=(coe*a[i][j])%MOD;
++ t;
for(int l=c-1; l>=j; --l)
{
a[k][l]=(a[k][l]*a[i][j]-a[i][l]*a[k][j])%MOD;
if(a[k][l]<0)
a[k][l]+=MOD;
}
}
++i;
}
}
for(i=1; i<MOD; ++i)
if((coe*i)%MOD==1)
break;
int result=i;
for(i=0; i<r; ++i)
result=(result*a[i][i])%MOD;
if(flag)
result =MOD-result;
return result;
}
struct point
{
int x,y;
};
inline int dis(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
inline int Direction(point pi,point pj,point pk) //判断向量PiPj在向量PiPk的顺逆时针方向 +顺-逆0共线
{
return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
inline bool On_Segment(point pi,point pj,point pk)
{
if(pk.x>=min(pi.x,pj.x)&&pk.x<=max(pi.x,pj.x)&&pk.y>=min(pi.y,pj.y)&&pk.y<=max(pi.y,pj.y))
return 1;
return 0;
}
int main()
{
MOD=10007;
point data[maxn];
int n,r,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&r);
r*=r;
memset(a,0,sizeof(a));
memset(map,0,sizeof(map));
for(int i=0; i<n; i++)
scanf("%d%d",&data[i].x,&data[i].y);
for(int i=0; i<n; i++)
for(int j=i+1; j<n; j++)
if(dis(data[i],data[j])<=r)
map[i][j]=1,map[j][i]=1;
for(int i=0; i<n; i++)
for(int j=i+1; j<n; j++)
for(int k=0; k<n; k++)
if(j!=k&&i!=k&&Direction(data[i],data[j],data[k])==0&&On_Segment(data[i],data[j],data[k]))
map[i][j]=0,map[j][i]=0;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
if(map[i][j])
a[i][j]=-1;
for(int i=0; i<n; i++)
{
int num=0;
for(int j=0; j<n; j++)
if(map[i][j])
num++;
a[i][i]=num;
}
int ans=gauss(n-1,n-1);
if(ans==0)
puts("-1");
else
printf("%d\n",ans);
}
return 0;
}