hdu 4082 Hou Yi's secret（亚洲赛北京赛区B题）

Hou Yi's secret

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 375????Accepted Submission(s): 120

Hou yi came back from God with ten magic arrows. He shot down nine suns, and the world returned to harmony. When Yao asked Hou Yi about the answer of his question, Hou Yi said: "God told me nothing. But I happened to see a 'life and death book' with your name on it. So I know the answer. But you know, I can't tell you because that's God's secret, and anyone who gives out God's secret will be burned by a thunder!"
Yao was very angry, he shouted: "But you promised me, remember?" Hou Yi said:
"Ooo-er, let's make some compromise. I can't tell you the answer directly, but I can tell you by my only precious magic arrow. I'll shoot the magic arrow several times on the ground, and of course the arrow will leave some holes on the ground. When you connect three holes with three line segments, you may get a triangle. The maximum number of similar triangles you can get means the number of years you can live from now on." (If the angles of one triangle are equal to the angles of another triangle respectively, then the two triangles are said to be similar.)
Yao was not good at math, but he believed that he could find someone to solve this problem. Would you help the great ancient Chinese emperor Yao?

?

#include <iostream>#include <stdio.h>#include <math.h>#include <memory.h>#include <algorithm>using namespace std;const double eps = 1e-6;struct point{ int x, y; bool tar; //tar是标记重复的点}p[25]; //点数很少，可以暴力struct triangle{ double ang[3];}t[8005]; //20*20*20 = 8000，不要开小了double dis(point a, point b) //求两点的距离{ return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}bool judge(double a, double b, double c) //判断是否三点能否组成三角形{ if(a + b <= c) return false; if(a + c <= b) return false; if(b + c <= a) return false; return true;}bool ok(triangle a, triangle b) //判断两个三角形是否相似，两个角相等就行{ if( fabs(a.ang[0] - b.ang[0]) < eps && fabs(a.ang[1] - b.ang[1]) < eps ) return true; return false;}bool hash[205][205], flag[8005];int main(){ int i, j, k, n, sum, tx, ty, temp, MAX; double a, b, c; while(scanf("%d", &n), n) { for(i = 0; i < n; i++) p[i].tar = false; memset(hash, false, sizeof(hash)); for(i = 0; i < n; i++) { scanf("%d %d", &p[i].x, &p[i].y); tx = p[i].x + 100; ty = p[i].y + 100; if(hash[tx][ty] == false) //hash判断是否有重复点 { hash[tx][ty] = true; p[i].tar = true; } } sum = 0; for(i = 0; i < n; i++) { if(!p[i].tar) continue; for(j = i + 1; j < n; j++) { if(!p[j].tar) continue; for(k = j + 1; k < n; k++) { if(!p[k].tar) continue; a = dis(p[i], p[j]); b = dis(p[j], p[k]); c = dis(p[i], p[k]); if(judge(a, b, c)) //3边能组成三角形 { //余弦定理求三角形的三个角 t[sum].ang[0] = acos((b*b+c*c-a*a)/(2*b*c)); t[sum].ang[1] = acos((a*a+c*c-b*b)/(2*a*c)); t[sum].ang[2] = acos((b*b+a*a-c*c)/(2*b*a)); sort(t[sum].ang, t[sum].ang + 3); sum++; } } } } memset(flag, false, sizeof(flag)); MAX = 0; for(i = 0; i < sum; i++) //开始求最大值 { if(flag[i]) continue; flag[i] = true; temp = 0; for(j = i; j < sum; j++) { if(ok(t[i], t[j])) { flag[j] = true; temp++; if(temp > MAX) MAX = temp; } } } printf("%d\n", MAX); } return 0;}

?

?

?

?