2011 ACM/ICPC 北京赛区现场赛 B题（hdu 4082）
KIDx 的解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4082

当时比赛提交第十六次过了

注意点：
①判定三角形合法性
②理解好题意：多个相同的点只算一个
③数组大小开足够大

#include <iostream>#include <algorithm>#include <cmath>using namespace std;#define EP 1e-8struct 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);    }}