Chrisoft::Blog(r#"ICPC类比赛中计算几何问题之「乱象」")

-虽然我还从未在博客里面写过一篇仅与ACM/ICPC相关的文章，但是今天情况发生了改变…… -

-今天打某神奇的「2018 ACM-ICPC 中国大学生程序设计竞赛暨丝绸之路程序设计竞赛」时， -遇到如下一题： -

-在三维空间内给出一个平面和N个点，在给定平面内移动的速度为v₂，在其余位置移动速度为v₁， -求按一定顺序走遍N个点并回到起点的最短所需时间。 -

-当然原题面大约是六级不到500的人写的，所以猜题意用了不少时间。但是摸清题意之后， -不就是计算几何套裸的TSP吗……于是让队友先写好TSP模板然后我去推计算几何的部分了。 -

-一开始非常智障地以为直接把点在平面上的投影点当落脚点就可以了，然而发现WA样例…… -（虽然已经猜到了结果）于是假设每一端分别少走一段距离，如下图： -

-此情形下每侧用时的变化量 -Δt=^p_cosα×v₁-^p×tanα_v₂。 -Δt'=p^{sinα×v₂-sin²α×v₁-cos²α×v₁}_{cos²α×v₁×v₂} -=p^{sinα×v₂-v₁}_{cos²α×v₁×v₂} -所以极值在sinα=^v₁_v₂时取得。~~管它是什么极大值还是极小值反正~~就用它好了。 -

-然后因为懒得找模板于是手推了许久点在平面上的投影公式。打完之后发现……TLE！ -然后发现队友写了递归的TSP……重写了非递归TSP之后秒过。~~顺便还抢到了一血。~~ -如果一定要看我的辣鸡代码的话，在这里。 -

-于是你就见识到了这道强行结合TSP的计算几何的奇葩题目。 -[1] -17年北京区域赛时也有一个判断线段是否与三角形内部有交集×bfs的题目也是神坑。 -

-不过高级别的比赛中的计算几何题目质量还是十分有保证的。像今年WF G题（疑似）用的Voronoi Diagram -[2]以及去年WF的A题。当然今年WF E题这种混合物理的题， -在官方发布数据之前我大概是过不了样例以外的任何测试点的（[3] -