题目链接:
http://acm./showproblem.php?pid=4082
题意:
给定n个点判断这些点能组成的三角形中,与同一个三角形相似的三角形的最大个数。
分析:
就是暴力枚举。但是写的时候要注意以下几点。
1)必须得能组成三角形。
2)去掉重复的点。。。被坑了,orz
代码如下:
#include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;const double eps = 1e-8;const int maxn = 20;struct point{double x,y;}p[maxn];struct triangle{double a[3];}t[maxn*maxn*maxn];int cross(point p0,point p1,point p2){return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}double dis(point p1,point p2){return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));}bool similar(triangle t1,triangle t2){if( (fabs(t1.a[0]*t2.a[1]-t1.a[1]*t2.a[0])<eps)&&(fabs(t1.a[1]*t2.a[2]-t1.a[2]*t2.a[1])<eps)&&(fabs(t1.a[0]*t2.a[2]-t1.a[2]*t2.a[0])<eps))return true;return false;}int main(){int n;while(~scanf("%d",&n)&&n){for(int i=0;i<n;i++){scanf("%lf%lf",&p[i].x,&p[i].y);for(int j=0;j<i;j++){if(p[i].x==p[j].x&&p[i].y==p[j].y){i--;n--;break;}}}int cnt = 0;if(n<3){puts("0");continue;}for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){for(int k=j+1;k<n;k++){if(cross(p[i],p[j],p[k])){t[cnt].a[0]=dis(p[i],p[j]);t[cnt].a[1]=dis(p[i],p[k]);t[cnt].a[2]=dis(p[j],p[k]);sort(t[cnt].a,t[cnt].a+3);cnt++;}}}}int ans = 0;for(int i=0;i<cnt;i++){int tmp = 1;for(int j=i+1;j<cnt;j++)if(similar(t[i],t[j]))tmp++;ans=max(ans,tmp);}printf("%d\n",ans);}return 0;}