hdu 4082 I Hou Yi's secret （计算几何）
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83295#problem/I
最多18个点，选3个点，能够成的三角形不超过1000个，O(n2)暴力就可以。
思路就是枚举三个点点，对于每一个构成的三角形，把这个三角形的最小角和次小角存起来。
然后枚举三角形，判断是否有两个三角形的最小角和次小角分别对应相等。
需要注意的是题目中问的是相似三角形的最大个数
如果A B 相似 C D 相似，但是B C 不相似，答案应该是2.
还有三角形自身和自身是相似的。
一开始求角度的时候只求了cos值，忘了求下acos了。
需要注意的是，枚举的到时候，三个点可能共线，这个还挺好，题目中说的是“** you may get a triangle**”
may算是提示了
如果共线，就不能构成三角形，何谈相似？
我共线的判断是用斜率搞的，特判下斜率不存在的情况（三个点的横坐标都相同）
然后又交，又WA....妈蛋。。。
然后想，会不会是他射到了同一个点上？
不管多少次射到同一个点上，就只会出现一个hole，也就算作一个点。
于是判重。
判重还没写全。
一开始只把因为重复而不能构成三角形的情况给cut掉了
就是枚举的三个点有至少两个一样，这个时候实际上只有两个点，所以不能够成三角形。
但是马上就发现，对于能构成的三角形的情况，一个点重复了几次，就算了几次，而实际上应该只算一次。
所以改在枚举之前判重。
至于精度问题，我是没遇到。。。
相等都是写成<=eqs 的形式了。。。
注意是fabs而不是abs
最后终于A了。
1
2
3
4 /* ***********************************************
5 Author :111qqz
6 Created Time :2016年03月03日 星期四 14时43分22秒
7 File Name :code/hdu/4082.cpp
8 ************************************************ */
9
10 #include<iostream>
11 #include<iomanip>
12 #include<cstdio>
13 #include<algorithm>
14 #include<cmath>
15 #include<cstring>
16 #include<string>
17 #include<map>
18 #include<set>
19 #include<queue>
20 #include<vector>
21 #include<stack>
22 #define y0 abc111qqz
23 #define y1 hust111qqz
24 #define yn hez111qqz
25 #define j1 cute111qqz
26 #define tm crazy111qqz
27 #define lr dying111qqz
28 using namespace std;
29 #define REP(i, n) for (int i=0;i<int(n);++i)
30 typedef long long LL;
31 typedef unsigned long long ULL;
32 const double eqs = 1E-6;
33 const int N = 25;
34 const int inf = 0x7fffffff;
35 int x[N],y[N];
36 int n;
37 double an[2000][5];
38 struct Q
39 {
40 int xx,yy;
41 }q[N];
42 double dis(int a,int b)
43 {
44 double res;
45 res = (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
46 res = sqrt(res);
47 return res;
48 }
49 double angle(double a,double b,double c)
50 {
51 double res;
52 res = (b*b+c*c-a*a)/(2*b*c);
53 // cout<<a<<" "<<b<<" "<<c<<" "<<res<<endl;
54 res = acos(res);
55 return res;
56 }
57
58 bool cmp(Q a,Q b)
59 {
60 if (a.xx<b.xx) return true;
61 if (a.xx==b.xx&&a.yy<b.yy) return true;
62 return false;
63 }
64 bool ok(int t)
65 {
66 if (q[t].xx==q[t+1].xx&&q[t].yy==q[t+1].yy)
67 return false;
68 return true;
69 }
70 int main()
71 {
72 while (scanf("%d",&n)!=EOF)
73 {
74 if (n==0) break;
75
76 // memset(ang,0,sizeof(ang));
77 // memset(angl,0,sizeof(angl));
78 memset(an,0,sizeof(an));
79 int sum = 0; //三角形的个数
80 for ( int i =1 ; i <= n ; i++ )
81 {
82 cin>>q[i].xx>>q[i].yy;
83 }
84 sort(q+1,q+n+1,cmp);
85 q[n+1].xx=inf;
86 q[n+1].yy=inf;
87
88 int n_dif=0;
89 for ( int i = 1; i <= n ; i++)
90 {
91 if (ok(i))
92 {
93 n_dif++;
94 x[n_dif]=q[i].xx;
95 y[n_dif]=q[i].yy;
96 }
97
98 }
99 n = n_dif;
100 // cout<<"n_dif:"<<n_dif<<endl;
101 for ( int i = 1 ; i <= n-2 ; i++ )
102 {
103 for ( int j = i + 1 ; j <= n-1 ; j++)
104 {
105 for ( int k = j +1 ; k <= n ; k++)
106 {
107 if (x[i]==x[j]&&y[i]==y[j]) continue;
108 if (x[i]==x[k]&&y[i]==y[k]) continue;
109 if (x[j]==x[k]&&y[j]==y[k]) continue; //难道还有一样的点？？？
110 if (x[i]==x[j]&&x[i]==x[k]) continue; //三点共线，且斜率不存在，构不成三角形。
111 //相同的三角形的点只算一个？
112 double k1,k2;
113 k1 = (y[i]-y[j])*1.0/(x[i]-x[j]);
114 k2 = (y[i]-y[k])*1.0/(x[i]-x[k]);
115 if (fabs(k1-k2)<=eqs) continue; //共线，不恩能够构成三角形
116 double si = dis(j,k);
117 double sj = dis(i,k);
118 double sk = dis(i,j);
119 double ai = angle(si,sj,sk);
120 double aj = angle(sj,si,sk);
121 double ak = angle(sk,si,sj);
122 double ang[10];
123 // cout<<"si:"<<si<<" sj:"<<sj<<" sk:"<<sk<<endl;
124 // cout<<"ai:"<<ai<<" aj:"<<aj<<" ak:"<<ak<<endl;
125 ang[0]=ai;
126 ang[1]=aj;
127 ang[2]=ak;
128 sort(ang,ang+3); //把角度从小到大排序
129 // angl[i][j][k][0]=ang[0];
130 // angl[i][j][k][1]=ang[1];
131 // angl[i][j][k][2]=ang[2]; //重要的是角度是多少，某个三角形是哪三个点得到的并不重要。
132 sum++;
133 an[sum][0]=ang[0];
134 an[sum][1]=ang[1];
135 an[sum][2]=ang[2];
136
137 }
138 }
139 }
140 int ans = 0; //初始是０不是１，因为可能恰好所有点共线，没有三角形，也就没有相似的三角形
141 if (sum!=0) ans = 1;
142 // for ( int i = 1 ; i <= sum ; i++ ) cout<<"an[i][0]"<<an[i][0]<<" an[i][1] "<<an[i][1]<<endl;
143 for ( int i = 1; i <= sum -1 ; i++ )
144 {
145 int cnt = 1;
146 for ( int j = i+1 ; j <= sum ; j++ )
147 {
148 double tmp1 = fabs(an[i][0]-an[j][0]);
149 double tmp2 = fabs(an[i][1]-an[j][1]);
150 if (tmp1<=eqs&&tmp2<=eqs)
151 {
152 cnt++;
153 }
154 ans = max(ans,cnt);
155 }
156 }
157 cout<<ans<<endl;
158
159 }
160 return 0;
161 }
162
163
164