传送门
就是求生成树的个数
在于建图，建立无向图，如果说两点之间有点，就不能建图，否则，两点之间建立边
也就是说点与点之间最多只有一条边，然后最多能构成一个完全图
首先判断两点之间的距离是否满足，然后判断三点是否贡献
最后利用矩阵树定理求解即可
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int N = 305;
const int mod = 10007;
int a[N][N], b[N][N];
ll pow(ll a, ll b, ll p){
ll ans = 1; a %= p;
while(b){
if(b & 1) ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
ll det(int a[][N], int n){
ll ans = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
a[i][j] = (a[i][j] % mod + mod) % mod;
for(int i = 1; i <= n; i++) {
int r = i;
for(int j = i; j <= n; j++) if(a[i][j] > a[r][i]) r = i;
if(r != i)
for(int j = 1; j <= n; j++) swap(a[i][j], a[r][j]);
if(a[i][i] == 0) return 0;
ll inv = pow(a[i][i], mod - 2, mod);
for(int j = i + 1; j <= n; j++) {
ll tmp = a[j][i] * inv % mod;
for(int k = i; k <= n; k++)
a[j][k] = (a[j][k] - a[i][k] * tmp % mod + mod) % mod;
}
ans = ans * a[i][i] % mod;
}
return ans;
}
struct Point{
int x, y;
Point(int x = 0, int y = 0):x(x),y(y){};
Point operator - (const Point &b) const {
return Point(x - b.x, y - b.y);
}
int operator ^ (const Point &b) const {
return x * b.y - y * b.x;
}
int operator * (const Point &b) const {
return x * b.x + y * b.y;
}
}p[N];
typedef Point Vector;
bool OnSegment(Point P1, Point P2, Point Q){//Q是否在线段P1P2上
return ((P1 - Q) ^ (P2 - Q)) == 0 && ((P1 - Q) * (P2 - Q)) <= 0;
}
int dis(Point a, Point b){
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
void solve(){
int n, r;
scanf ("%d%d", &n, &r);
for (int i = 1; i <= n; i++)
scanf ("%d%d", &p[i].x, &p[i].y);
memset (a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (dis(p[i], p[j]) > r * r) continue;
int k = 0;
for (k = 1; k <= n; k++) {
if (k == i || k == j) continue;
if (OnSegment(p[i], p[j], p[k])) break;
}
if (k == n + 1) a[i][j] = a[j][i] = 1;
}
}
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (a[i][j])
++b[i][i], ++b[j][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
b[i][j] -= a[i][j];
int ans = det(b, n - 1);
printf ("%d
", ans ? ans : -1);
}
int main(){
int t;
scanf("%d", &t);
while(t--) solve();
}