2016多校训练Contest5:1004 How Many Triangles

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5784

题目翻译

屏幕上有 N 个点,求问这些点能组成多少个三角形。 ( 3n2000 && 0xi,yi1e9 )

题解

需要知道一个奇怪的结论, 三角形个数 = ( 锐角数量 – 钝角&直角数量 × 2 ) ÷ 3
于是,问题转化为了如何求平面内的钝角/直角/锐角。
首先,我们枚举每个角的顶点,通过这个顶点,把其他店都变成向量,那么现在的所有角就是任意两个向量的夹角了。然后,我们再枚举两个向量中的第一个向量,通过计算的二个向量的个数,来得到钝角/直角/锐角的数量。通过把这些向量极角排序,我们发现可以有单调性,于是复杂度就有了保证。 O(n^2logn)

代码