HDU 4305

能够构成边的前提:

1. 距离<=R
2. 两点之间的直线上,没有其他点阻碍.

---

• 存点.然后2层for遍历每个点.建边

  判断2点直线上是否存在其他点

• 根据2个点的x坐标的的大小,将xa,ya存下左边点,xb,yb存下右边的点.
• 遍历除取这2个点之外的点.首先根据每个点的x坐标是否处于xa,xb中间来判断是否可能阻断2点的连线(只有在2点中间才可能在2点所连接的直线上)
• 左边点和遍历到的点的斜率=(ya - ty)/(xa - tx)
遍历到的点和右边点的斜率=(ty - yb)/(tx - xb)
• 为了避免可能出现分母=0,把分母移到对面来,k1 k2
• Matrix-tree定理求生成树个数

  #include <iostream>
  #include <algorithm>
  #include <string.h>
  #include <math.h>
  using namespace std;
  const int maxn = 305;
  #define ll long long 
  #define mod 10007
  ll b[maxn][maxn];
  int n, r;
  // 学过线代都知道求行列式的方法之一就是化成上\下三脚矩阵,对角线元素乘积是行列式值
  ll determina(int n) {
  	ll res = 1;
  	for (int i = 1; i <= n; i++) {
  		if (!b[i][i]) { //若果对角线元素为0,把此行都一都移到下一行去
  			bool flag = false;
  			for (int j = i + 1; j <= n; j++) { //从i+1行开始找i列中的第一个不为0的元素，与现在的行交换
  				if (b[j][i]) {//找到了该列不为0的元素,
  					flag = 1; //标记,交换
  					for (int k = i; k <= n; k++) swap(b[i][k], b[j][k]);
  					res = -res;// 换行系数变为负数
  					break; //退出.
  				}
  			}
  			if (!flag) return 0; //这一行全部为0,行列式值为0
  		}
  		for (int j = i + 1; j <= n; j++) {
  			while (b[j][i]) { //从下面的行找一个不为0的元素与第i行进行消元
  				ll t = b[i][i] / b[j][i];
  				for (int k = i; k <= n; k++) {
  					b[i][k] = (b[i][k] - t * b[j][k]) % mod;
  					swap(b[i][k], b[j][k]);//消元后,把0的行换到下面来。
  				}
  				res = -res;
  			}
  		}
  		res *= b[i][i];//对角线元素相乘
  		res %= mod;
  	}
  	return (res + mod) % mod;
  }
  struct point {
  	int x, y;
  }points[maxn];
  double getdis(point& t1,point& t2) {
  	return sqrt(1.0*(t1.x - t2.x)*(t1.x - t2.x) + 1.0*(t1.y - t2.y)*(t1.y - t2.y));
  }
  bool check(int a,int b) {
  	int xa = points[a].x, xb = points[b].x;
  	int ya = points[a].y, yb = points[b].y;
  	if (xa > xb) { //不管高低,把xa换成左边的点
  		swap(xa, xb); swap(ya,yb);
  	}
  	for (int i = 1; i <= n; i++) {
  		if (i==a || i==b) continue;
  		int tx = points[i].x, ty = points[i].y;
  		if (xa <= tx && tx <= xb) { //x在范围内,
  			int k1 = (ya - ty) * (tx - xb);
  			int k2 = (ty - yb) * (xa - tx);
  			if (k1 == k2) return 0;
  		}
  	}
  	return 1;
  }
  int main() {
  //	freopen("a.txt","r",stdin);
  	int times; cin >> times;
  	while (times--) {
  		memset(b, 0, sizeof b);
  //		memset(points,0,sizeof points);
  		scanf("%d%d", &n, &r); 
  		for (int i = 1; i <= n; i++) scanf("%d%d",&points[i].x,&points[i].y);
  		for (int i = 1; i <= n; i++) {
  			for (int j = 1; j <= n; j++) {
  				if (i == j) continue;
  				double dis = getdis(points[i],points[j]);
  				if (check(i, j) && dis <= r) {
  					b[i][i]++; b[i][j]-=1;
  				}
  			}
  		}
  		ll ans = determina(n-1);
  		printf("%lld\n",ans>0?ans:-1);
  	}
  	return 0;
  }