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}),这时候点对在向量的两侧。而向量是双向的,所以一个多边形对点对在向量两边是计数次数为2*2=4次,在同侧计数次数为2*4=8次。

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

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

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

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

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

代码如下: