HDU 4305 Lighting(生成树计数+点在线段判断)_综合

题目链接：
HDU 4305 Lighting
题意：
给出 $n$ 个点的横纵坐标和距离 $R$ ，只有当两个点满足距离 $\leq R$ 且这两个点连线上没有其他点时这两个点才能建边，求将这 $n$ 个点连通的生成数个数？答案对 $10007$ 取模。
数据范围： $n\leq 300, R \leq 2000$ 。
分析；
同样一段代码 $G++$ 能过， $C++就TLE$ ！太坑了=_=！
需要用到简单的计算几何判断一个是否在一条线段上。
然后建边用 $Matrix-Tree定理$ 搞搞就好。
下面求 $det$ 的函数的消元方式可以避免求逆元(因为要取模),很是神奇！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const ll mod = 10007;
const int MAX_N = 310;
const double eps = 1e-6;int degree[MAX_N];
ll C[MAX_N][MAX_N];int sgn(double x)
{if(fabs(x) < eps) return 0;else if(x < 0) return -1;else return 1;
}struct Point{double x, y;Point () {}Point (double _x, double _y) : x(_x), y(_y) {}Point operator - (const Point& rhs) const {return Point(x - rhs.x, y - rhs.y);}Point operator + (const Point& rhs) const {return Point(x + rhs.x, y + rhs.y);}Point operator * (const double d) const {return Point(x * d, y * d);}double dis(const Point& rhs) const {return hypot(x - rhs.x, y - rhs.y);}double dot(const Point& rhs) const { //点积return x * rhs.x + y * rhs.y;}double cross(const Point& rhs) const { //叉积return x * rhs.y - y * rhs.x;}
}point[MAX_N];struct Line{Point st, ed;Line () {}Line (Point _st, Point _ed): st(_st), ed(_ed) {}int on_seg(const Point& rhs) const {return sgn((rhs - st).cross(ed - st)) == 0 && sgn((rhs - st).dot(rhs - ed)) <= 0;}
};ll det(ll mat[][MAX_N], int n)
{for(int i = 0; i < n; ++i) {for(int j = 0; j < n; ++j) {mat[i][j] = (mat[i][j] % mod + mod) % mod;}}ll res = 1;int cnt = 0;for(int i = 0; i < n; ++i) {for(int j = i + 1; j < n; ++j) {while(mat[j][i]) {ll t = mat[i][i] / mat[j][i];for(int k = i; k < n; ++k) {mat[i][k] = (mat[i][k] - mat[j][k] * t) % mod;swap(mat[j][k], mat[i][k]);}cnt++;}}if(mat[i][i] == 0) return -1;res = mat[i][i] * res % mod;}if(cnt & 1) res = -res;return (res + mod) % mod;
}int main()
{int T, n;double R;scanf("%d", &T);while(T--) {scanf("%d%lf", &n, &R);for(int i = 0; i < n; ++i) {scanf("%lf%lf", &point[i].x, &point[i].y);}memset(degree, 0, sizeof(degree));memset(C, 0, sizeof(C));for(int i = 0; i < n; ++i) {for(int j = 0; j < n; ++j) {if(i == j) continue;if(point[i].dis(point[j]) > R) continue;//还要判断i点和j点之间没有其他点int flag = 1;Line line = Line(point[i], point[j]);for(int k = 0; k < n; ++k) {if(k == i || k == j) continue;if(line.on_seg(point[k])) {flag = 0;break;}}if(flag == 0) continue;degree[i]++;C[i][j]--;}C[i][i] = degree[i];}printf("%lld\n", det(C, n - 1));}return 0;
}