From 9d3c8c0e6e1a7ba43bf3dc19350d1dca68b657a3 Mon Sep 17 00:00:00 2001 From: Chris Xiong Date: Sun, 10 Feb 2019 11:16:07 +0800 Subject: Initial commit. --- blog/post/2018-04-22.html | 188 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 188 insertions(+) create mode 100644 blog/post/2018-04-22.html (limited to 'blog/post/2018-04-22.html') diff --git a/blog/post/2018-04-22.html b/blog/post/2018-04-22.html new file mode 100644 index 0000000..7311f13 --- /dev/null +++ b/blog/post/2018-04-22.html @@ -0,0 +1,188 @@ + + + + +Chrisoft::Blog + + + + + + + + + + + + + + + + + + + + +
+ +
+
+

ICPC类比赛中计算几何问题之「乱象」

+
2018-04-22
#garbage #acmicpc
+
+ +
+

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

+

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

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

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

+

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

+
+ +
+

+此情形下每侧用时的变化量 +Δt=pcosα×v1-p×tanαv2。 +Δt'=psinα×v2-sin2α×v1-cos2α×v1cos2α×v1×v2 +=psinα×v2-v1cos2α×v1×v2 +所以极值在sinα=v1v2时取得。管它是什么极大值还是极小值反正就用它好了。 +

+

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

+

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

+

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

+
+ +

+
[1]: 其实这套题目总体质量并不高……
[2]: 「疑似」是因为我还没写
[3]: 现在数据发布了，搞到数据立即发现起点坐标读反了以及多写了一对fabs。面向数据编程真好。
+
+ +
+
+
+ \ No newline at end of file -- cgit v1.2.3