链接:https://ac.nowcoder.com/acm/contest/52441/E 来源:牛客网 给定n 个不重复的坐标,求其中 3个坐标能表示一个等腰三角形的组数。 三点共线不算三角形,等边三角形为特殊的等腰三角形。用c++实现

时间: 2023-05-25 18:02:39 浏览: 159
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N=10005; const double eps=1e-8; struct point { double x,y; friend bool operator<(const point &a,const point &b) { return a.x<b.x||(a.x==b.x&&a.y<b.y); } friend point operator+(const point &a,const point &b) { return point{a.x+b.x,a.y+b.y}; } friend point operator-(const point &a,const point &b) { return point{a.x-b.x,a.y-b.y}; } friend point operator*(const point &a,double b) { return point{a.x*b,a.y*b}; } friend point operator/(const point &a,double b) { return point{a.x/b,a.y/b}; } friend double operator*(const point &a,const point &b) { return a.x*b.y-a.y*b.x; } }p[N],st[N],st2[N]; int top=0,top2=0,n,ans; double len[N],sum[N]; inline double dist(const point &a,const point &b) { double x=a.x-b.x,y=a.y-b.y; return sqrt(x*x+y*y); } inline void tubao() { for(int i=1;i<=n;++i) { while(top&&p[i].y<=st[top].y) --top; st[++top]=p[i]; } for(int i=1;i<=n;++i) { while(top2&&p[i].y>=st2[top2].y) --top2; st2[++top2]=p[i]; } } int main() { scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%lf%lf",&p[i].x,&p[i].y); sort(p+1,p+n+1); tubao(); for(int i=1;i<=top;++i) st[i+top]=st[i]; for(int i=1,j=1,k=1;i<=top;++i) { while(dist(st[i],st[j])<dist(st[i],st[j+1])) j=j%top+1; while(k+1<i+top&&((st[i]-st[j])*(st[i]-st[k+1]))>((st[i]-st[j])*(st[i]-st[k]))) k=k%top+1; len[i]=dist(st[i],st[j]); sum[i]=sum[i-1]+len[i]; while(sum[i]-sum[j-1]>len[i]+eps) ++j; if(st[i].y==st[j].y) continue; double a=dist(st[i],st[j]),b=dist(st[j],st[k]),c=dist(st[i],st[k]),p=(a+b+c)/2; if(fabs(b*b+c*c-a*a)<eps) ans+=upper_bound(sum+i,sum+top2+1,sum[i-1]+len[i]/2)-lower_bound(sum+i,sum+top2+1,sum[i-1]-len[i]/2); else continue; } printf("%d\n",ans); return 0; }

相关推荐

对于这道题,我们可以考虑对输入的每两个点求出它们的中点,然后把这个中点作为哈希表的键值,值为一个列表,存储所有能与该中点构成等腰三角形的点。具体做法如下: 1. 枚举每两个点,计算它们的中点,把该中点作为哈希表的键值,值为一个空列表。 2. 遍历所有点,如果该点与中点的距离等于某个已有中点的距离,则将该点加入到对应的列表中。 3. 对于每个中点对应的列表,如果列表长度大于等于2,则说明存在能与该中点构成等腰三角形的点,计算组合数并累加到答案中。 时间复杂度为 $O(n^2 \log n)$,其中 $n$ 为点的个数。具体实现细节可以参考下面的代码: python from collections import defaultdict import math n = int(input()) points = [] for i in range(n): x, y = map(int, input().split()) points.append((x, y)) # 计算两点之间的距离 def dist(p1, p2): return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) # 构建哈希表 hash_map = defaultdict(list) for i in range(n): for j in range(i + 1, n): p1, p2 = points[i], points[j] mid = ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2) hash_map[mid] = [] # 遍历所有点 for i in range(n): for j in range(i + 1, n): p1, p2 = points[i], points[j] mid = ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2) for k in range(n): if k != i and k != j: p3 = points[k] d1, d2 = dist(p1, p3), dist(p2, p3) if abs(d1 - d2) < 1e-6: hash_map[mid].append(p3) # 计算答案 ans = 0 for mid, points in hash_map.items(): if len(points) >= 2: n = len(points) ans += n * (n - 1) // 2 print(ans)
这是一个经典的图论问题,可以使用染色法来解决。具体来说,我们可以从任意一个格子开始,将其染成红色,然后将其相邻的格子染成绿色,再将与绿色格子相邻的格子染成蓝色,以此类推。这样染色的过程中,每个格子的颜色都只与其相邻的格子有关,因此不会出现相邻格子颜色相同的情况。 根据染色法的思路,我们可以得到一个递推式:设f[i][j][k]表示第i行第j列的格子染成颜色k(k=0表示红色,k=1表示绿色,k=2表示蓝色)的涂色方案数,则有: f[i][j][0] = f[i-1][j][1] + f[i-1][j][2] + f[i][j-1][1] + f[i][j-1][2] f[i][j][1] = f[i-1][j][0] + f[i-1][j][2] + f[i][j-1][0] + f[i][j-1][2] f[i][j][2] = f[i-1][j][0] + f[i-1][j][1] + f[i][j-1][0] + f[i][j-1][1] 其中,第一行和第一列的格子需要特殊处理,即: f[1][j][0] = f[1][j-1][1] + f[1][j-1][2] f[1][j][1] = f[1][j-1][0] + f[1][j-1][2] f[1][j][2] = f[1][j-1][0] + f[1][j-1][1] f[i][1][0] = f[i-1][1][1] + f[i-1][1][2] f[i][1][1] = f[i-1][1][0] + f[i-1][1][2] f[i][1][2] = f[i-1][1][0] + f[i-1][1][1] 最终的答案即为f[m][n][0] + f[m][n][1] + f[m][n][2]。 这个问题可以用动态规划来解决,具体实现可以参考以下代码: int f[105][105][3]; int main() { int m, n; scanf("%d%d", &m, &n); memset(f, 0, sizeof(f)); f[1][1][0] = f[1][1][1] = f[1][1][2] = 1; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (i == 1 && j == 1) continue; f[i][j][0] = f[i-1][j][1] + f[i-1][j][2] + f[i][j-1][1] + f[i][j-1][2]; f[i][j][1] = f[i-1][j][0] + f[i-1][j][2] + f[i][j-1][0] + f[i][j-1][2]; f[i][j][2] = f[i-1][j][0] + f[i-1][j][1] + f[i][j-1][0] + f[i][j-1][1]; f[i][j][0] %= MOD; f[i][j][1] %= MOD; f[i][j][2] %= MOD; } } printf("%d\n", (f[m][n][0] + f[m][n][1] + f[m][n][2]) % MOD); return 0; }

最新推荐

基于Springboot的网上宠物店系统的设计与实现论文-java-文档-基于Springboot网上宠物店系统的设计与实现文档

基于Springboot的网上宠物店系统的设计与实现论文-java-文档-基于Springboot网上宠物店系统的设计与实现文档论文: !!!本文档只是论文参考文档! 需要项目源码、数据库sql、开发文档、毕设咨询等,请私信联系~ ① 系统环境:Windows/Mac ② 开发语言:Java ③ 框架:SpringBoot ④ 架构:B/S、MVC ⑤ 开发环境:IDEA、JDK、Maven、Mysql ⑥ JDK版本:JDK1.8 ⑦ Maven包:Maven3.6 ⑧ 数据库:mysql 5.7 ⑨ 服务平台:Tomcat 8.0/9.0 ⑩ 数据库工具:SQLyog/Navicat ⑪ 开发软件:eclipse/myeclipse/idea ⑫ 浏览器:谷歌浏览器/微软edge/火狐 ⑬ 技术栈:Java、Mysql、Maven、Springboot、Mybatis、Ajax、Vue等 最新计算机软件毕业设计选题大全 https://blog.csdn.net/weixin_45630258/article/details/135901374 摘 要 目 录 第1章

DAC简介及参考电路PPT学习教案.pptx

DAC简介及参考电路PPT学习教案.pptx

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire

OceanBase数据库简介及原理解析

# 1. OceanBase数据库概述 ## 1.1 OceanBase数据库的发展历程 OceanBase数据库是由阿里巴巴集团自主研发的一款分布式关系型数据库系统,起源于阿里集团的业务需求和技术挑战。自2010年开始研发,经过多年的迭代和优化,OceanBase已经成为阿里巴巴集团重要的核心数据库产品之一。在实际的业务场景中,OceanBase已经被广泛应用于金融、电商、物流等各个领域。 ## 1.2 OceanBase数据库的特点和优势 OceanBase数据库具有以下特点和优势: - **分布式架构**:OceanBase采用多副本分布式架构,可以实现高可用和数据容灾。 -

python的pandas读取excel怎么将excel表里的列从1开始而不是0

在 Pandas 中,数据框的列默认从0开始编号,但我们可以通过自定义函数来进行数据列的转换。可以先将读取的数据框列的第一个值设为1,然后对后续列进行递增处理。 以下是示例代码: ```python import pandas as pd # 读取 Excel 文件 df = pd.read_excel('your_excel_file.xlsx') # 定义函数将列从1开始 def reset_column(x): return str(int(x) + 1) # 应用函数到所有列名 df = df.rename(columns=reset_column) # 打印数据框

第三章薪酬水平、薪酬系统的运行与控制.pptx

第三章薪酬水平、薪酬系统的运行与控制.pptx

"互动学习:行动中的多样性与论文攻读经历"

多样性她- 事实上SCI NCES你的时间表ECOLEDO C Tora SC和NCESPOUR l’Ingén学习互动,互动学习以行动为中心的强化学习学会互动,互动学习,以行动为中心的强化学习计算机科学博士论文于2021年9月28日在Villeneuve d'Asq公开支持马修·瑟林评审团主席法布里斯·勒菲弗尔阿维尼翁大学教授论文指导奥利维尔·皮耶昆谷歌研究教授:智囊团论文联合主任菲利普·普雷教授,大学。里尔/CRISTAL/因里亚报告员奥利维耶·西格德索邦大学报告员卢多维奇·德诺耶教授,Facebook /索邦大学审查员越南圣迈IMT Atlantic高级讲师邀请弗洛里安·斯特鲁布博士,Deepmind对于那些及时看到自己错误的人...3谢谢你首先,我要感谢我的两位博士生导师Olivier和Philippe。奥利维尔,"站在巨人的肩膀上"这句话对你来说完全有意义了。从科学上讲,你知道在这篇论文的(许多)错误中,你是我可以依

理解MVC架构:Laravel框架的核心设计

# 1. 第1章 项目立项与概述 ## 1.1 动机 随着互联网的快速发展,Web应用的开发需求不断增加。为了提高开发效率、代码可维护性和团队协作效率,我们决定采用MVC架构来设计我们的Web应用。 ## 1.2 服务器状态 我们的服务器环境采用了LAMP(Linux + Apache + MySQL + PHP)架构,满足了我们Web应用开发的基本需求,但为了更好地支持MVC架构,我们将对服务器进行适当的配置和优化。 ## 1.3 项目立项 经过团队讨论和决定,决定采用Laravel框架来开发我们的Web应用,基于MVC架构进行设计和开发,为此做出了项目立项。 ## 1.4 项目概况

如何将HDFS上的文件读入到Hbase,用java

要将HDFS上的文件读入到HBase,可以使用Java编写MapReduce程序实现,以下是实现步骤: 1. 首先需要创建一个HBase表,可使用HBase Shell或Java API创建; 2. 编写MapReduce程序,其中Map阶段读取HDFS上的文件,将数据转换成Put对象,然后将Put对象写入到HBase表中; 3. 在MapReduce程序中设置HBase表名、列族名、列名等参数; 4. 在程序运行前,需要将HBase相关的jar包和配置文件加入到classpath中; 5. 最后提交MapReduce任务运行即可。 以下是示例代码: ``` Configuration

酒店餐饮部工作程序及标准(某酒店).doc

餐饮