whust#2 I Hou Yi's secret-白红宇

whust#2 I Hou Yi's secret

阅读量：4313 次

发布时间：2019-06-06

本文共 1635 字，大约阅读时间需要 5 分钟。

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了。

/*************************************************************************    > File Name: code/whust/#2/I.cpp    > Author: 111qqz    > Email: rkz2013@126.com     > Created Time: Wed 22 Jul 2015 12:29:35 PM CST ************************************************************************/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #define y0 abc111qqz#define y1 hust111qqz#define yn hez111qqz#define j1 cute111qqz#define tm crazy111qqz#define lr dying111qqzusing namespace std;#define REP(i, n) for (int i=0;i
                 
                  >q[i].xx>>q[i].yy; } sort(q+1,q+n+1,cmp); q[n+1].xx=inf; q[n+1].yy=inf; int n_dif=0; for ( int i = 1; i <= n ; i++) { if (ok(i)) { n_dif++; x[n_dif]=q[i].xx; y[n_dif]=q[i].yy; } } n = n_dif; // cout<<"n_dif:"<
                  
                   <