kuangbin专题八 HDU4305 Lightning（生成树计数+三点共线）

本文主要是介绍kuangbin专题八 HDU4305 Lightning（生成树计数+三点共线），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
给出n个点的坐标，距离不超过r的点如果中间没有其它点则可以连一条边，最后求生成树的数量，对10007取模。
题解：
这道题，，实在强大，我完全一脸蒙逼，看了大佬的题解之后，我也不想写啥了，以后回来看题解的话，还是直接去看大佬写的博客吧，这道题也逼着我去学了一回逆元，但是我那个生成树计数模板好像是不需要逆元的。。。ORZ
P1(x1,y1)、P2(x2,y2)、P3(x3,y3)三点共线的条件为：
(y2-y1)/(x2-x1)=(y3-y1)/(x3-x1)
下面是大佬的博客：
https://www.cnblogs.com/flipped/p/5767113.html

另外我还是照样发上去我的丑逼代码吧。。。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define LL long long int
const LL mod=10007;
const int MAXN=305;
const double inf=100000000;
struct point
{double x,y;
}p[MAXN];
LL B[MAXN][MAXN];
double map[MAXN][MAXN];
LL determinant(int n)//原来这个模板是不用逆元的。。。ORZ 
{LL res=1;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){while(B[j][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)%mod;swap(B[i][k],B[j][k]);}res=-res;}}if(!B[i][i]) return -1;//表示有一个机器人没有超载 res=res*B[i][i]%mod;}return (res+mod)%mod;
} 
bool same(point a,point b,point c)//判断三点公式和如果共线的话，b是否在a和c之间。 
{return ((b.y-a.y)*(c.x-a.x)==(c.y-a.y)*(b.x-a.x)//三点共线公式 &&min(a.x,c.x)<=b.x&&max(a.x,c.x)>=b.x//下面这两个是判断在三点共线的前提下，b是否在a和c之间。 &&min(a.y,c.y)<=b.y&&max(a.y,c.y)>=b.y);
} 
int main()
{int n,t;double R;scanf("%d",&t);while(t--){scanf("%d%lf",&n,&R);memset(B,0,sizeof(B)); for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){if(sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y))<=R){bool flag=true;for(int k=1;k<=n;k++)if(k!=i&&k!=j&&same(p[i],p[k],p[j]))flag=false;if(flag){B[i][j]=B[j][i]=-1;B[i][i]++,B[j][j]++;} }}LL  ans=determinant(n-1); printf("%lld\n",ans);               }
}