题解 UVA12123 【Magnetic Train Tracks】

2019-08-27 20:22:43


感觉...挺傻逼的?

锐角三角形和直角三角形似乎不是很好数的亚子,可以考虑拿总数 $n\choose 3$ 减掉钝角三角形的数量。

枚举一个点 $A$ ,按极角序枚举另一个点 $B$ ,那么极角在 $(ang_B+\frac{\pi}{2},ang_B+\pi)$ 范围内的点 $C$ 都可以和 $A,B$ 组成一个钝角三角形。 那么直接拿两个指针扫一下就好了。可以发现这样计数是不重不漏的。

另外这题有点卡精度,比较的时候注意加一个 $\epsilon$ 。

代码见blog