[USACO Open10]数三角形Triangle Counting解题报告

题目


分析

这道题的要点在于:含原点的三角形不好数,我们数不含原点的三角形,最后用C(N,3)扣掉它就是答案了。

怎么数“不含原点的三角形”呢?

画出我们所在的坐标系。我们拿一条过原点的直线l,按极角序去扫描:



直线l分成两条射线,一个是a,另一个是b。它绕着原点(Bessie所在点)旋转,请自行想象在孙悟空手中旋转的金箍棒。
(猴哥,猴哥,你真了不得……)

然后关键在于:每当射线a扫到一个点P时,我们统计P和直线l“左侧”所有点形成的三角形(严格地讲,是和a叉积为正的半平面):



像这样,图中展示了a扫到p点时统计的三个三角形。

每一个不包含原点的三角形——无论形状多么畸形,位置多么奇特,总会被计入统计一次且只有一次。下面展示了几个三角形,和它们被计入统计时,扫描线a的位置:



(注意,这个点不一定是极角最小的点)

这样问题就好办了:先把所有点按照极角排序,然后线性扫描下去,用两个指针维护a和b的位置,在扫描的过程中,减掉所有应予统计的三角形。

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注