首页 > 代码库 > [HDU 4082] Hou Yi's secret (简单计算几何)

[HDU 4082] Hou Yi's secret (简单计算几何)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4082

题目大意:

给你n个点,问能最多构成多少个相似三角形。

 

用余弦定理,计算三个角度,然后暴力数有多少个,更新答案。

 

代码:

  1 #include <cstdio>  2 #include <cmath>  3 #include <algorithm>  4 #include <cstring>  5 #include <vector>  6 #include <set>  7 using namespace std;  8 typedef pair<int,int> PII;  9 typedef long long LL; 10  11 #define EPS 1e-8 12 #define PB push_back 13  14 struct POINT{ 15     int x,y; 16     double dis(const POINT& b){ 17         return sqrt( double(x-b.x)*double(x-b.x)+double(y-b.y)*double(y-b.y) ); 18     } 19     POINT(int ax=0,int ay=0):x(ax),y(ay){} 20     bool operator==(const POINT &b) const{ 21         return x==b.x&&y==b.y; 22     } 23     bool operator<(const POINT &b) const{ 24         if( x==b.x ) return y<b.y; 25         return x<b.x; 26     } 27 }; 28  29 struct triangle{ 30     double cosa[3]; 31     triangle(){} 32  33     triangle(POINT a,POINT b,POINT c){ 34         double A = a.dis(b); 35         double B = a.dis(c); 36         double C = b.dis(c); 37  38         cosa[0] = (A*A+B*B-C*C)/(2*A*B); 39         cosa[1] = (B*B+C*C-A*A)/(2*B*C); 40         cosa[2] = (A*A+C*C-B*B)/(2*A*C); 41         sort(cosa,cosa+3); 42     } 43  44     triangle(double a,double b,double c){ 45         cosa[0] = a; 46         cosa[1] = b; 47         cosa[2] = c; 48         sort(cosa,cosa+3); 49     } 50  51     bool operator==(const triangle& b) const{ 52         return fabs(cosa[0]-b.cosa[0])<EPS&&fabs(cosa[1]-b.cosa[1])<EPS&&fabs(cosa[2]-b.cosa[2])<EPS; 53     } 54  55 }; 56  57 bool isLine(POINT a,POINT b,POINT c){ 58     return (c.x-a.x)*(b.y-a.y) == (b.x-a.x)*(c.y-a.y); 59 } 60  61 POINT pt[20]; 62 int n; 63  64 int main(){ 65     while( scanf("%d",&n)!=EOF && n ){ 66         set<POINT> st; 67         int ptrb = 0; 68         for(int i=0;i<n;i++){ 69             int x,y; 70             scanf("%d%d",&x,&y); 71             if( st.find(POINT(x,y))==st.end() ){ 72                 pt[ptrb++] = POINT(x,y); 73                 st.insert(POINT(x,y)); 74             } 75         } 76  77  78         vector<triangle> vec; 79         for(int i=0;i<ptrb;i++){ 80             for(int j=i+1;j<ptrb;j++){ 81                 for(int k=j+1;k<ptrb;k++){ 82                     if( !isLine(pt[i],pt[j],pt[k])){ 83                         vec.PB(triangle(pt[i],pt[j],pt[k])); 84                     } 85                 } 86             } 87         } 88  89         int maxn = 0; 90  91         for(size_t i=0;i<vec.size();i++){ 92             int as = 1; 93  94             for(size_t j=i+1;j<vec.size();j++){ 95                 if( vec[i]==vec[j] ) as++; 96             } 97             maxn = max(as,maxn); 98         } 99         printf("%d\n",maxn);100     }101     return 0;102 }

 

[HDU 4082] Hou Yi's secret (简单计算几何)