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多次。
相关文章
- SqlBulkCopy – The given value of type String from the data source cannot be converted to type
- HDU 3336 Count the string 解题报告
- ORA-02172: The PUBLIC keyword is not appropriate for a disable thread ORACLE 报错 故障修复 远程处理
- ORA-31053: The value of the depth argument in the operator cannot be negative ORACLE 报错 故障修复 远程处理
- ORA-39054: missing or invalid definition of the SQL output file. ORACLE 报错 故障修复 远程处理
- ORA-41642: Missing “string” element in the rule condition ORACLE 报错 故障修复 远程处理
- ORA-46014: The value of the “aclFile” element is too long. ORACLE 报错 故障修复 远程处理
- ORA-48464: The predicate buffer reached the maximum length [string] ORACLE 报错 故障修复 远程处理
- ORA-48488: The predicate string exceeds the maximum length [string] ORACLE 报错 故障修复 远程处理
- ORA-02820: Unable to write the requested number of blocks ORACLE 报错 故障修复 远程处理
- ORA-13033: Invalid data in the SDO_ELEM_INFO_ARRAY in SDO_GEOMETRY object ORACLE 报错 故障修复 远程处理
- ORA-13663: The task string contains no results for execution string. ORACLE 报错 故障修复 远程处理
- ORA-13906: The tablespace is not of the right type. ORACLE 报错 故障修复 远程处理
- Enjoy the Power of CC1 Linux: Unleash Your Potential(cc1linux)
- 修复 Ubuntu 中 “E: The package cache file is corrupted, it has the wrong hash”
- Discover the Latest Advancements in Oracle 12.2 Database Technology(oracle12.2)
- Exploring the Data Types Stored in Redis: A Comprehensive Guide(redis存放什么数据)
- Exploring the Benefits of BC Linux for Your Computing Needs!(bclinux)
- 尝试攻克決勝難關The A to Z of Redis(the a什么redis)