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

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz