KIDx 的解题报告
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4082
当时比赛提交第十六次过了
注意点:
①判定三角形合法性
②理解好题意:多个相同的点只算一个
③数组大小开足够大
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define EP 1e-8
struct point{ //点
double x, y;
}p[20];
struct trangle{ //三角形(特征:2个角的(余弦值*2))
double A, B;
}tra[10005];
bool hash[205][205], vis[10005];
double dist (point a, point b) //欧式距离求边长
{
return sqrt ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
bool multi (point a, point b, point c) //叉积判断三点是否共线
{
double x1, y1, x2, y2;
x1 = b.x - a.x;
y1 = b.y - a.y;
x2 = c.x - b.x;
y2 = c.y - b.y;
int tp = x1 * y2 - x2 * y1;
if (tp == 0)
return false;
return true;
}
bool similar (trangle a, trangle b) //余弦值对应比较判定相似,2个角即可
{
if (fabs (a.A-b.A) <= EP && fabs (a.B-b.B) <= EP)
return true;
return false;
}
int main()
{
double e[3];
int n, i, j, k, num, tp, maxs;
while (scanf ("%d", &n), n)
{
memset (hash, false, sizeof(hash));
for (i = 0; i < n; i++)
{
scanf ("%lf%lf", &p[i].x, &p[i].y);
if (hash[(int)p[i].x+100][(int)p[i].y+100]) //出现过的点就不再要了
i--, n--;
hash[(int)p[i].x+100][(int)p[i].y+100] = true;
}
num = 0; //累计合法三角形个数
for (i = 0; i < n; i++) //获取所有合法三角形存放到tra
{
for (j = i + 1; j < n; j++)
{
for (k = j + 1; k < n; k++)
{
if (!multi (p[i], p[j], p[k])) //判定三角形合法性
continue;
e[0] = dist (p[i], p[j]);
e[1] = dist (p[i], p[k]);
e[2] = dist (p[j], p[k]);
sort (e, e+3); //三边排序实现对应比较
double a = e[0];
double b = e[1];
double c = e[2];
tra[num].A = (b*b + c*c - a*a)/b/c; //直接用(余弦值*2)对应判定
tra[num].B = (a*a + c*c - b*b)/a/c;
num++;
}
}
}
maxs = 0;
memset (vis, false, sizeof(vis));
for (i = 0; i < num; i++) //以一个三角形为基准往下比较数相似三角形
{
if (vis[i]) //已经访问过的就不必再以它为准了
continue;
tp = 1;
for (j = i + 1; j < num; j++)
{
if (vis[j])
continue;
if (similar (tra[i], tra[j]))
tp++, vis[j] = true;
}
if (tp > maxs)
maxs = tp;
}
printf ("%d\n", maxs);
}
}
- 大小: 2 KB
- 大小: 6.1 KB
分享到:
相关推荐
"ACM/ICPC的教学与实践" ACM/ICPC是国际大学生程序设计竞赛的缩写,全球公认的规模最大、水平最高的国际大学生程序设计竞赛。该项竞赛旨在使大学生运用计算机来充分展示自己分析问题和解决问题的能力。ACM/ICPC被...
### ACM/ICPC常用算法的代码库(吉林大学版,强烈推荐) #### 概述 这份文档提供了由吉林大学计算机科学与技术学院整理的一套针对ACM/ICPC竞赛的算法代码库。它包含了多种算法及其实现方式,适用于ACM/ICPC参赛者的...
《ACM/ICPC题集》是吉林大学计算机科学学院在2005年精心制作的一份宝贵资源,专门针对ACM(国际大学生程序设计竞赛)/ICPC(国际大学生程序设计竞赛)进行训练和学习。这个压缩包包含了一本名为“ACM.pdf”的文档,...
中国在ACM/ICPC赛事中取得了显著成就,北京大学、清华大学、浙江大学等高校的队伍多次在全球总决赛中名列前茅,显示了中国在计算机科学教育领域的实力。 总的来说,ACM/ICPC大赛不仅是全球计算机科学学子展现才华的...
《ACM/ICPC全球总决赛试题集锦》是编程竞赛领域的瑰宝,它汇集了从1992年至2008年ACM国际大学生程序设计竞赛(ACM International Collegiate Programming Contest,简称ACM/ICPC)全球总决赛的全部试题。这个珍贵的...
《ACM/ICPC竞赛训练》是北京大学暑期课程的一个重要组成部分,主要针对计算机科学领域内的算法竞赛进行深度训练。在这些课程中,"搜索"是一个核心主题,涉及到一系列的算法和策略,旨在解决复杂的问题。这里我们将...
### ACM/ICPC竞赛训练(北京大学暑期夏令营内容一览) #### 一、概述 ACM/ICPC(国际大学生程序设计竞赛)是一项面向全球大学生的计算机编程与算法设计比赛,旨在通过解决复杂的计算问题来培养学生的创新能力和...
2008年ACM-ICPC(国际大学生程序设计竞赛)成都赛区的现场赛,是一场集结了顶尖编程人才的激烈竞技。该比赛旨在挑战参赛者的算法设计、问题解决和编程技能,对于参赛者来说,这不仅是技术的较量,也是团队协作与策略...
《ACM/ICPC 文章集合》 这篇文章集合聚焦于ACM(国际大学生程序设计竞赛)和ICPC(国际大学生程序设计竞赛),这两项赛事是全球范围内最具影响力的大学生编程比赛,旨在培养和展示参赛者的算法设计、问题解决以及...
ACM/ICPC2009 拉丁美洲区域赛 包含输入输出数据 题目PDF文档 详细解题报告+答案代码TXT文档 有一半是水题,2、3个比较难的 大家可以拿来做做 其中的输入输出数据,可以放到那个离线OJ系统去判断你的程序对错。(离线...
The 36th ACM/ICPC Asia Regional Shanghai Site —— Online Contest Problem Set
【ACM/ICPC 入门详解】 ACM/ICPC(国际大学生程序设计竞赛/国际编程竞赛)是一项全球性的编程比赛,旨在培养大学生的算法设计、问题解决和团队合作能力。初学者若想踏入这个领域,首先要了解基础的编程知识和如何在...
ACM/ICPC中国*辽宁第二届大学生程序设计竞赛题目
2010年ACM/ICPC珠海区域赛决赛题目
首先,我们要理解ACM/ICPC比赛的题型,通常包括算法题、数据结构题、数学题等。解题报告会详细介绍每个问题的背景,阐述问题的核心所在,比如需要解决的主要计算问题,或者涉及的特定数据结构。例如,hdu题目可能...
**ACM/ICPC培训讲义**是针对国际大学生程序设计竞赛(ACM/ICPC)准备的一份重要参考资料,旨在提升参赛者在算法和程序设计方面的能力。这份讲义涵盖了多个关键领域的知识,包括**搜索算法**、**计算几何**、**动态...
2011年的华中南赛区ACM/ICPC邀请赛与“永新视博”杯程序设计大赛是该区域内的一项重要赛事,吸引了众多高校的参赛队伍。解题报告是参赛者对比赛中遇到的问题和解决方案进行总结和分析的文档,对于提升编程技巧和学习...
在ACM/ICPC竞赛中,图论问题是常见的题目来源,涉及到的问题包括最短路径、最小生成树、网络流、拓扑排序等。最大矩阵乘积问题虽然表面上可能不直接涉及图,但在优化策略中,可以借助图论的思想,如贪心选择和动态...
【ACM/ICPC微型Judge系统详解】 在编程竞赛领域,特别是ACM(国际大学生程序设计竞赛)/ICPC(国际大学生程序设计竞赛)中,Judge系统扮演着至关重要的角色。它负责评判参赛团队提交的代码是否能正确解决特定问题。...