The 35th ACM/ICPC Asia Regional Tianjin Site —— Online Contest 1009 Convex 解题报告

The 35th ACM/ICPC Asia Regional Tianjin Site —— Online Contest

2010年天津赛 网络赛 I题 Convex

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3629

题目大意是给你700个点，问从中选4个点组成凸四边形的方法数

比赛的时候其实最终得到了正确的方法，结果因为写搓了导致TLE，HDU的64位整形必须用I64d，导致WA

最直接的方法是枚举，复杂度O(n^4),但是显然会TLE

然后我们用了1个多小时想出了O(n^3)的解法，然后试了一次，TLE，最后是ben1222（不愧是大师级啊），在听完我的思路后瞬间优化到O(n^2 log2(n))

首先解释O(n^3)的解法

我们可以任选两个点组成一个向量，然后统计另两个点的点对

很容易看出，对于凸多边形，以凸多边形边为选定向量，另两个点为点对各计数了一次（比如向量ab，点对{c,d}），这时候另两个点在向量的同一侧；以对角线为选定向量，另两个点为为点对各计数一次（比如向量ac，点对{b,d}），这时候点对在向量的两侧。而向量是双向的，所以一个多边形对点对在向量两边是计数次数为22=4次，在同侧计数次数为24=8次。

同理，对于凹多边形一个多边形对点对在向量两边是计数次数为23=6次，在同侧计数次数为23=6次。

显然如果点对在向量两边是计数次数只和为D，同侧计数次数和为S，凸四边形的个数就是(S-D) / 4,因为对凹四边形计数数量一样，就可以消去。

同时，对于向量而言，令左边的点数为tpl，右边点数为tpr，同侧点对的数量就是C2(tpl)+C2(tpr),两侧点对的数量就是tpl*tpr，然而直接对枚举向量枚举计算点是 O(n^3)的，会TLE，所以还要做个优化。

实际上，可以先枚举向量起点，然后对剩余点做犄角排序，然后剩下的枚举终点，而其中左边和右边的点可以计算出来。

还有几个要注意的地方，开始我写搓了，写了个3n^2+3n^2log2(n)，得TLE了，后来优化到2*n^2+n^2log2(n)就过了，时间1500ms，还有就是HDU的64bit整形输出必须是I64d，否则也会TLE，我因为这个TLE的N多次。