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

2024-02-02 08:38

本文主要是介绍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);               }
}

这篇关于kuangbin专题八 HDU4305 Lightning(生成树计数+三点共线)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/670125

相关文章

Flask 验证码自动生成的实现示例

《Flask验证码自动生成的实现示例》本文主要介绍了Flask验证码自动生成的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习... 目录生成图片以及结果处理验证码蓝图html页面展示想必验证码大家都有所了解,但是可以自己定义图片验证码

Python如何在Word中生成多种不同类型的图表

《Python如何在Word中生成多种不同类型的图表》Word文档中插入图表不仅能直观呈现数据,还能提升文档的可读性和专业性,本文将介绍如何使用Python在Word文档中创建和自定义各种图表,需要的... 目录在Word中创建柱形图在Word中创建条形图在Word中创建折线图在Word中创建饼图在Word

nginx生成自签名SSL证书配置HTTPS的实现

《nginx生成自签名SSL证书配置HTTPS的实现》本文主要介绍在Nginx中生成自签名SSL证书并配置HTTPS,包括安装Nginx、创建证书、配置证书以及测试访问,具有一定的参考价值,感兴趣的可... 目录一、安装nginx二、创建证书三、配置证书并验证四、测试一、安装nginxnginx必须有"-

Java实战之利用POI生成Excel图表

《Java实战之利用POI生成Excel图表》ApachePOI是Java生态中处理Office文档的核心工具,这篇文章主要为大家详细介绍了如何在Excel中创建折线图,柱状图,饼图等常见图表,需要的... 目录一、环境配置与依赖管理二、数据源准备与工作表构建三、图表生成核心步骤1. 折线图(Line Ch

浅析如何使用Swagger生成带权限控制的API文档

《浅析如何使用Swagger生成带权限控制的API文档》当涉及到权限控制时,如何生成既安全又详细的API文档就成了一个关键问题,所以这篇文章小编就来和大家好好聊聊如何用Swagger来生成带有... 目录准备工作配置 Swagger权限控制给 API 加上权限注解查看文档注意事项在咱们的开发工作里,API

Java使用POI-TL和JFreeChart动态生成Word报告

《Java使用POI-TL和JFreeChart动态生成Word报告》本文介绍了使用POI-TL和JFreeChart生成包含动态数据和图表的Word报告的方法,并分享了实际开发中的踩坑经验,通过代码... 目录前言一、需求背景二、方案分析三、 POI-TL + JFreeChart 实现3.1 Maven

MybatisGenerator文件生成不出对应文件的问题

《MybatisGenerator文件生成不出对应文件的问题》本文介绍了使用MybatisGenerator生成文件时遇到的问题及解决方法,主要步骤包括检查目标表是否存在、是否能连接到数据库、配置生成... 目录MyBATisGenerator 文件生成不出对应文件先在项目结构里引入“targetProje

Python使用qrcode库实现生成二维码的操作指南

《Python使用qrcode库实现生成二维码的操作指南》二维码是一种广泛使用的二维条码,因其高效的数据存储能力和易于扫描的特点,广泛应用于支付、身份验证、营销推广等领域,Pythonqrcode库是... 目录一、安装 python qrcode 库二、基本使用方法1. 生成简单二维码2. 生成带 Log

Python使用Pandas库将Excel数据叠加生成新DataFrame的操作指南

《Python使用Pandas库将Excel数据叠加生成新DataFrame的操作指南》在日常数据处理工作中,我们经常需要将不同Excel文档中的数据整合到一个新的DataFrame中,以便进行进一步... 目录一、准备工作二、读取Excel文件三、数据叠加四、处理重复数据(可选)五、保存新DataFram

SpringBoot生成和操作PDF的代码详解

《SpringBoot生成和操作PDF的代码详解》本文主要介绍了在SpringBoot项目下,通过代码和操作步骤,详细的介绍了如何操作PDF,希望可以帮助到准备通过JAVA操作PDF的你,项目框架用的... 目录本文简介PDF文件简介代码实现PDF操作基于PDF模板生成,并下载完全基于代码生成,并保存合并P