HDU - 4082 Hou Yi's secret

題意：求最多有多少的相似三角形

思路：枚舉的情況下加上余弦定理，還有的就是要去重，相似的話，我們只要判斷較小的兩個角相等就行了，當然還要有精度的考慮

#include 
#include 
#include 
#include 
#include 
using namespace std;
const double eps=1e-6;
const int MAXN = 8005;

struct point{
	int x,y;
	bool tar;
}p[25];

struct triangle{
	double ang[3];
}t[MAXN];
int hash[205][205],flag[MAXN],n;

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));
}

int judge(double a, double b, double c){
	if (a+b <= c)
		return 0;
	if (a+c <= b)
		return 0;
	if (b+c <= a)
		return 0;
	return 1;
}

int ok(triangle a, triangle b){  
	if (fabs(a.ang[0]-b.ang[0]) < eps && fabs(a.ang[1]-b.ang[1]) < eps)
		return 1;
	return 0;
}

int main(){
	double a,b,c;
	while (scanf("%d", &n) != EOF && n){
		for (int i = 0; i < n; i++)
			p[i].tar = 0;
		memset(hash,0,sizeof(hash));
		for (int i = 0; i < n; i++){
			scanf("%d%d", &p[i].x, &p[i].y);
			int tx = p[i].x + 100;
			int ty = p[i].y + 100;
			if (!hash[tx][ty]){
				hash[tx][ty] = 1;
				p[i].tar = 1;
			}
		}
		int sum = 0;
		for (int i = 0; i < n; i++){
			if (!p[i].tar)
				continue;
			for (int j = i+1; j < n; j++){
				if (!p[j].tar)
					continue;
				for (int 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)){
						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((a*a+b*b-c*c)/(2*a*b));
						sort(t[sum].ang,t[sum].ang+3);
						sum++;
					}
				}
			}
		}
		memset(flag,0,sizeof(flag));
		int Max = 0;
		for (int i = 0; i < sum; i++){
			if (flag[i])
				continue;
			flag[i] = 1;
			int temp = 0;
			for (int j = i; j < sum; j++){
				if (ok(t[i],t[j])){
					flag[j] = 1;
					temp++;
					if (temp > Max)
						Max = temp;
				}
			}
		}
		printf("%d\n",Max);
	}
	return 0;
}