1.题目链接。题目大意:给定平面上n个点和一个距离r,任意两个点之间有边的条件是:两个点的欧几里得距离小于等于r并且这两个点之间的连线不再有其他的点。然后问有多少种方法使得所有的点都联通。
2.显然,这个图的每个生成树都是满足条件的,所以这个题其实就是在问(假设已经连边连好了),给定的这个图有多少棵生成树??关于生成树的计数问题,似乎有个Cayley定理,他说一个n个点的完全图有n^(n-2)棵生成树,其实这个定理的证明方法,可以采用无向图的Prufer序列的性质证明,也可以采用我们本题的Matrix-Tree定理。
3.Matrix-Tree定理告诉我们:一个图的生成树的数量和一个矩阵有关,这个矩阵就是该图的基尔霍夫矩阵,一个图的基尔霍夫矩阵等于这个图的度数矩阵-邻接矩阵。得到这个矩阵之后,生成树的数量就是这个矩阵任意n-1阶行列式的值。至于证明,就算了,因为有点复杂。
4。那么回到这个题,我们首先建图,建图其实还是很简单的,直接n^3建图,对于每两个点,枚举一下中间点,判断是不是有共线的存在,如果没有,那么就我们就没必要在构建度数矩阵和邻接矩阵,直接构建基尔霍夫矩阵就行(PS:防止有的童鞋看不懂代码,我解释一下怎么直接构建基尔霍夫矩阵,因为度数矩阵的定义是V[i][i]就是代表第i个点的度数,所以这个矩阵只有对角线上有值,其他的地方都是0,而邻接矩阵,只要是这个地方有边,就是1.可以看出无向图的邻接矩阵是一个对称矩阵,所以当用度数矩阵-邻接矩阵时,对于每对点(i,j),如果是存在边的,那么基尔霍夫矩阵对角线上mat[i][i],mat[j][j]要加一,而对应(i,j),(j,i)这里就是-1,因为我们保证i!=j.并且度数矩阵这里一定是0,所以减一就是-1)然后构造好矩阵之后,求一下行列式的值就行了,至于行列式的值怎么求,这个方法多种,不再深入探究。
#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
using namespace std;
const int M = 10007;//模数
const int N = 301;//点数
int mat[N][N];
//计算一个n*n的行列式的值。
int det(int c[][N], int n)
{
int i, j, k, t, ret = 1;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) c[i][j] %= M;
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++)
while (c[j][i])
{
t = c[i][i] / c[j][i];
for (k = i; k < n; k++)
c[i][k] = (c[i][k] - c[j][k] * t) % M;
swap(c[i], c[j]);
ret = -ret;
}
if (c[i][i] == 0)
return 0;
ret = ret * c[i][i] % M;
}
return (ret + M) % M;
}
struct point {
int x, y;
}p[N];
int same(point a, point b, point c)
{
return (a.x - c.x) * (b.y - c.y) == (b.x - c.x) * (a.y - c.y)
&& min(a.x, c.x) <= b.x && max(a.x, c.x) >= b.x
&& min(a.y, c.y) <= b.y && max(a.y, c.y) >= b.y;
}
double dis(point a, point b)
{
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n, r;
memset(mat, 0, sizeof(mat));
scanf("%d%d", &n, &r);
for (int i = 0; i < n; i++)
{
scanf("%d%d", &p[i].x, &p[i].y);
}
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (dis(p[i], p[j]) <= r)
{
int flag = 1;
for (int k = 0; k < n; k++)
{
if (k != j && k != i && same(p[i], p[j], p[k]))
{
flag = 0;
}
}
if (flag)
{
mat[i][j] = -1;
mat[j][i] = -1;
mat[i][i]++;
mat[j][j]++;
}
}
}
}
int ans = det(mat, n - 1);
if (ans == 0)
{
cout << -1 <<endl;
}
else
{
cout << ans << endl;
}
}
}