2011 ACM/ICPC 北京赛区现场赛 B题（hdu 4082）
KIDx 的解题报告题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4082
当时比赛提交第十六次过了http://dl.iteye.com/upload/attachment/587189/ad2a389c-dc3d-39ac-b7ec-23cbcaa70688.jpg
注意点：
①判定三角形合法性
②理解好题意：多个相同的点只算一个
③数组大小开足够大
http://dl.iteye.com/upload/attachment/591356/c95d42ea-0569-3f4c-88ef-6a5f5ea42e0b.png
#include <iostream>#include <algorithm>#include <cmath>using namespace std;#define EP 1e-8struct point{ //点 double x, y;}p;struct trangle{ //三角形（特征：2个角的(余弦值*2)） double A, B;}tra;bool hash, vis;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; 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.x, &p.y); if (hash[(int)p.x+100][(int)p.y+100])//出现过的点就不再要了 i--, n--; hash[(int)p.x+100][(int)p.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, p, p)) //判定三角形合法性 continue; e = dist (p, p); e = dist (p, p); e = dist (p, p); sort (e, e+3);//三边排序实现对应比较 double a = e; double b = e; double c = e; tra.A = (b*b + c*c - a*a)/b/c; //直接用(余弦值*2)对应判定 tra.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)//已经访问过的就不必再以它为准了 continue; tp = 1; for (j = i + 1; j < num; j++) { if (vis) continue; if (similar (tra, tra)) tp++, vis = true; } if (tp > maxs) maxs = tp; } printf ("%d\n", maxs); }}
页:
[1]