首页 > 代码库 > HDU 4082 Hou Yi's secret --枚举
HDU 4082 Hou Yi's secret --枚举
题意: 给n个点,问最多有多少个相似三角形(三个角对应相等)。
解法: O(n^3)枚举点,形成三角形,然后记录三个角,最后按三个角度依次排个序,算一下最多有多少个连续相等的三元组就可以了。
注意:在同一个坐标的两点只算一次,所以要判一下。
代码:
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define eps 1e-8using namespace std;#define N 100017struct Point{ double x,y; Point(double x=0, double y=0):x(x),y(y) {} void input() { scanf("%lf%lf",&x,&y); }};typedef Point Vector;int dcmp(double x) { if(x < -eps) return -1; if(x > eps) return 1; return 0;}template <class T> T sqr(T x) { return x * x;}Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); }Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); }bool operator < (const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }bool operator >= (const Point& a, const Point& b) { return a.x >= b.x && a.y >= b.y; }bool operator <= (const Point& a, const Point& b) { return a.x <= b.x && a.y <= b.y; }bool operator == (const Point& a, const Point& b) { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; }double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }double Length(Vector A) { return sqrt(Dot(A, A)); }double Angle(Vector A, Vector B) { return (Dot(A, B) / Length(A) / Length(B)); }double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }//data segmentstruct Tri{ double A[3]; Tri(double x,double y,double z) { A[0] = x, A[1] = y, A[2] = z; } Tri(){} bool operator <(const Tri& a)const { if(dcmp(A[0]-a.A[0]) == 0) { if(dcmp(A[1]-a.A[1])==0) return dcmp(A[2]-a.A[2])<0; return dcmp(A[1]-a.A[1])<0; } return dcmp(A[0]-a.A[0])<0; }}t[3005];bool operator == (const Tri& a,const Tri& b) { return dcmp(a.A[0]-b.A[0]) == 0 && dcmp(a.A[1]-b.A[1]) == 0 && dcmp(a.A[2]-b.A[2]) == 0; }Point p[25];int tot,n;//data endsint mp[300][300];int main(){ int i,j,k; int a[5]; while(scanf("%d",&n)!=EOF && n) { memset(mp,0,sizeof mp); tot = 0; int cntt=1; for(i=1;i<=n;i++) { int a,b;scanf("%d%d",&a,&b); if(mp[a+100][b+100]==0) p[cntt].x=a,p[cntt++].y=b; mp[a+100][100+b]=1; } n=cntt-1; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { for(k=j+1;k<=n;k++) { Point A = p[i], B = p[j], C = p[k]; if(A == B || A == C || B == C) continue; if(dcmp(Cross(B-A,C-A)) == 0) continue; double ang1 = Angle(B-A,C-A); double ang2 = Angle(A-B,C-B); double ang3 = Angle(A-C,B-C); double A1 = min(ang1,min(ang2,ang3)); double A3 = max(ang1,max(ang2,ang3)); double A2 = ang1+ang2+ang3-A1-A3; t[++tot] = Tri(A1,A2,A3); } } } sort(t+1,t+tot+1); int Maxi = (tot!=0), cnt = 1; for(i=2;i<=tot;i++) { if(t[i] == t[i-1]) cnt++; else cnt = 1; Maxi = max(Maxi,cnt); } cout<<Maxi<<endl; } return 0;}
HDU 4082 Hou Yi's secret --枚举
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。