2011 北京现场赛 B Hou Yi's secret

本文主要是介绍2011 北京现场赛 B Hou Yi's secret，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//题意：输入n个点，求最多的相似三角形个数

//数据很小，直接暴力，但是有两个trick，点的共线和重合问题。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const double EP=1e-8;
struct Point{double x, y;}p[20];
struct T{Point p[3];double ang[3];}t[1000];
int f[300][300];
double cross(Point sp, Point ep, Point op){
    return (sp.x-op.x)*(ep.x-op.x)+(sp.y-op.y)*(ep.y-op.y);
}
double dist(Point p1, Point p2){
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double x_mult(Point sp, Point ep, Point op){
return (sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y);
}
T make(Point p1, Point p2, Point p3){
    T tt;
    tt.p[0]=p1;tt.p[1]=p2;tt.p[2]=p3;
    tt.ang[0]=acos(cross(p1, p2, p3)/dist(p1, p3)/dist(p2, p3));
    tt.ang[1]=acos(cross(p1, p3, p2)/dist(p1, p2)/dist(p3, p2));
    tt.ang[2]=acos(cross(p3, p2, p1)/dist(p1, p3)/dist(p2, p1));
    return tt;
}

bool comp(int i, int j){

    sort(t[i]. ang, t[i].ang+3);
    if((fabs(t[i].ang[0]-t[j].ang[0])<EP)&&
        (fabs(t[i].ang[1]-t[j].ang[1])<EP)&&
        (fabs(t[i].ang[2]-t[j].ang[2])<EP))
    return true;
    while(next_permutation(t[i].ang, t[i].ang+3)){
    if((fabs(t[i].ang[2]-t[j].ang[0])<EP)&&
       (fabs(t[i].ang[1]-t[j].ang[1])<EP)&&
       (fabs(t[i].ang[0]-t[j].ang[2])<EP))
       return true;
          }
    return false;
}
int main(){
//freopen("1.txt", "r", stdin);
    int n, i, j, k, sum, s, ans, t1, t2, tsum;
    while(scanf("%d", &tsum)&&tsum){
  n=0;memset(f, 0, sizeof(f));
        for(i=0; i<tsum; i++){
            scanf("%d%d", &t1, &t2);
   if(f[t1+100][t2+100])continue;
   f[t1+100][t2+100]=1;
   p[n].x=t1*1.0;p[n].y=t2*1.0;
   n++;
        }
        sum=0;
        for(i=0; i<n-2; i++)
        for(j=i+1; j<n-1; j++)
        for(k=j+1; k<n; k++){
   if(fabs(x_mult(p[i], p[j], p[k]))>EP)
            t[sum++]=make(p[i], p[j], p[k]);
        }
        ans=0;
        for(i=0; i<sum; i++){
            s=0;
        for(j=0; j<sum; j++){
            if(comp(i, j))
            s++;
        }
        if(ans<s)ans=s;
        }
        printf("%d\n", ans);
    }
    return 0;
}