首页 > 代码库 > [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 (简单计算几何)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。