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

69 阅读 0 评论 46 点赞

我是靠谱客的博主鲤鱼毛衣，最近开发中收集的这篇文章主要介绍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("%lldn",ans);               
    }
}