hdu 4082 I Hou Yi's secret (计算几何)

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83295#problem/I

最多18个点,选3个点,能够成的三角形不超过1000个,O(n2)暴力就可以。

思路就是枚举三个点点,对于每一个构成的三角形,把这个三角形的最小角和次小角存起来。

然后枚举三角形,判断是否有两个三角形的最小角和次小角分别对应相等。

需要注意的是题目中问的是相似三角形的最大个数

如果A  B 相似 C D 相似,但是B C 不相似,答案应该是2.

还有三角形自身和自身是相似的。

一开始求角度的时候只求了cos值,忘了求下acos了。

需要注意的是,枚举的到时候,三个点可能共线,这个还挺好,题目中说的是“** you may get a triangle**”

may算是提示了

如果共线,就不能构成三角形,何谈相似?

我共线的判断是用斜率搞的,特判下斜率不存在的情况(三个点的横坐标都相同)

然后又交,又WA....妈蛋。。。

然后想,会不会是他射到了同一个点上?

不管多少次射到同一个点上,就只会出现一个hole,也就算作一个点。

于是判重。

判重还没写全。

一开始只把因为重复而不能构成三角形的情况给cut掉了

就是枚举的三个点有至少两个一样,这个时候实际上只有两个点,所以不能够成三角形。

但是马上就发现,对于能构成的三角形的情况,一个点重复了几次,就算了几次,而实际上应该只算一次。

所以改在枚举之前判重。

至于精度问题,我是没遇到。。。

相等都是写成<=eqs 的形式了。。。

注意是fabs而不是abs

最后终于A了。

  1
  2    
  3    
  4    /* ***********************************************
  5    Author :111qqz
  6    Created Time :2016年03月03日 星期四 14时43分22秒
  7    File Name :code/hdu/4082.cpp
  8    ************************************************ */
  9    
 10    #include<iostream>
 11    #include<iomanip>
 12    #include<cstdio>
 13    #include<algorithm>
 14    #include<cmath>
 15    #include<cstring>
 16    #include<string>
 17    #include<map>
 18    #include<set>
 19    #include<queue>
 20    #include<vector>
 21    #include<stack>
 22    #define y0 abc111qqz
 23    #define y1 hust111qqz
 24    #define yn hez111qqz
 25    #define j1 cute111qqz
 26    #define tm crazy111qqz
 27    #define lr dying111qqz
 28    using namespace std;
 29    #define REP(i, n) for (int i=0;i<int(n);++i)  
 30    typedef long long LL;
 31    typedef unsigned long long ULL;
 32    const double eqs = 1E-6;
 33    const int N = 25;
 34    const int inf = 0x7fffffff;
 35    int x[N],y[N];
 36    int n;
 37    double an[2000][5];
 38    struct Q
 39    {
 40        int xx,yy;
 41    }q[N];
 42    double dis(int a,int b)
 43    {
 44        double res;
 45        res = (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
 46        res = sqrt(res);
 47        return res;
 48    }
 49    double angle(double a,double b,double c)
 50    {
 51        double res;
 52    	  res = (b*b+c*c-a*a)/(2*b*c);
 53       // cout<<a<<" "<<b<<" "<<c<<" "<<res<<endl;
 54    	  res = acos(res);
 55        return res;
 56    }
 57    
 58    bool cmp(Q a,Q b)
 59    {
 60        if (a.xx<b.xx) return true;
 61        if (a.xx==b.xx&&a.yy<b.yy) return true;
 62        return false;
 63    }
 64    bool ok(int t)
 65    {
 66        if (q[t].xx==q[t+1].xx&&q[t].yy==q[t+1].yy)
 67    	  return false;
 68        return true;
 69    }
 70    int main()
 71    {
 72        while (scanf("%d",&n)!=EOF)
 73     {  
 74    	  if (n==0) break;
 75    
 76     //   memset(ang,0,sizeof(ang));
 77     //   memset(angl,0,sizeof(angl));
 78        memset(an,0,sizeof(an));
 79        int sum = 0; //三角形的个数
 80        for ( int i =1 ; i <= n ; i++ )
 81        {
 82    	  cin>>q[i].xx>>q[i].yy;
 83        }
 84        sort(q+1,q+n+1,cmp);
 85        q[n+1].xx=inf;
 86        q[n+1].yy=inf;
 87    
 88        int n_dif=0;
 89        for ( int i = 1; i <= n ; i++)
 90        {
 91    	  if (ok(i))
 92    	  {
 93    		n_dif++;
 94    		x[n_dif]=q[i].xx;
 95    		y[n_dif]=q[i].yy;
 96    	  }
 97    
 98        }
 99        n = n_dif;
100       // cout<<"n_dif:"<<n_dif<<endl;
101        for ( int i = 1 ; i <= n-2  ; i++ )
102        {
103    	  for ( int j = i + 1 ; j <= n-1 ; j++)
104    	  {
105    		for ( int k = j +1 ; k <= n ; k++)
106    		{
107    		    if (x[i]==x[j]&&y[i]==y[j]) continue;
108    		    if (x[i]==x[k]&&y[i]==y[k]) continue;
109    		    if (x[j]==x[k]&&y[j]==y[k]) continue; //难道还有一样的点???
110    		    if (x[i]==x[j]&&x[i]==x[k]) continue;  //三点共线,且斜率不存在,构不成三角形。
111    		    //相同的三角形的点只算一个?
112    		    double k1,k2;
113    		    k1 = (y[i]-y[j])*1.0/(x[i]-x[j]);
114    		    k2 = (y[i]-y[k])*1.0/(x[i]-x[k]);
115    		    if (fabs(k1-k2)<=eqs) continue;   //共线,不恩能够构成三角形
116    		    double si = dis(j,k);
117    		    double sj = dis(i,k);
118    		    double sk = dis(i,j);
119    		    double ai = angle(si,sj,sk);
120    		    double aj = angle(sj,si,sk);
121    		    double ak = angle(sk,si,sj);
122    		    double ang[10];
123    		 //   cout<<"si:"<<si<<" sj:"<<sj<<" sk:"<<sk<<endl;
124    		 //   cout<<"ai:"<<ai<<" aj:"<<aj<<" ak:"<<ak<<endl;
125    		    ang[0]=ai;
126    		    ang[1]=aj;
127    		    ang[2]=ak;
128    		    sort(ang,ang+3); //把角度从小到大排序
129    		 //   angl[i][j][k][0]=ang[0];
130    		 //   angl[i][j][k][1]=ang[1];
131    		 //   angl[i][j][k][2]=ang[2];       //重要的是角度是多少,某个三角形是哪三个点得到的并不重要。
132    		    sum++;
133    		    an[sum][0]=ang[0];
134    		    an[sum][1]=ang[1];
135    		    an[sum][2]=ang[2];
136    		    
137    		}
138    	  }
139        }
140        int ans = 0;  //初始是0不是1,因为可能恰好所有点共线,没有三角形,也就没有相似的三角形
141        if (sum!=0) ans = 1;
142     //   for ( int i = 1 ; i <= sum ; i++ ) cout<<"an[i][0]"<<an[i][0]<<"  an[i][1] "<<an[i][1]<<endl; 
143        for ( int i = 1; i <= sum -1 ; i++ )
144        {
145    	  int cnt = 1;
146    	  for ( int j = i+1 ; j <= sum ; j++ )
147    	  {
148    		double tmp1 = fabs(an[i][0]-an[j][0]);
149    		double tmp2 = fabs(an[i][1]-an[j][1]);
150    		if (tmp1<=eqs&&tmp2<=eqs)
151    		{
152    		    cnt++;
153    		}
154    		ans = max(ans,cnt);
155    	  }
156        }
157        cout<<ans<<endl;
158    		
159    }
160    	return 0;
161    }
162
163
164