1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
<!DOCTYPE html><html><head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<meta name="theme-color" content="#000000">
<title>Chrisoft::Blog(r#"ICPC类比赛中计算几何问题之「乱象」")</title>
<meta name="description" content="«ICPC类比赛中计算几何问题之「乱象」» de spelunca ursae visere">
<meta name="author" content="Chris Xiong">
<script type="text/javascript" src="/panel.js"></script>
<script type="text/javascript" src="/themer.js"></script>
<script type="text/javascript" src="/blog/footnoter.js"></script>
<script type="text/javascript" src="/blog/aes-js.js"></script>
<script type="text/javascript" src="/blog/scrypt.js"></script>
<script type="text/javascript" src="/blog/sha256.js"></script>
<script type="text/javascript" src="/blog/decryptor.js"></script>
<link rel="stylesheet" type="text/css" href="/common.css">
<link rel="stylesheet" type="text/css" href="/panel.css">
<link rel="stylesheet" type="text/css" href="/theme0a.css" id="theme0a">
<link rel="stylesheet" type="text/css" href="/theme0b.css" id="theme0b">
<link rel="stylesheet" type="text/css" href="/theme1a.css" id="theme1a">
<link rel="stylesheet" type="text/css" href="/theme1b.css" id="theme1b">
<link rel="stylesheet" type="text/css" href="/theme2a.css" id="theme2a">
<link rel="stylesheet" type="text/css" href="/theme2b.css" id="theme2b">
<link rel="stylesheet" type="text/css" href="/theme3a.css" id="theme3a">
<link rel="stylesheet" type="text/css" href="/theme3b.css" id="theme3b">
<link rel="stylesheet" type="text/css" href="/blog/blogext.css">
<script>
function ol()
{
window.onresize=function()
{
if(window.innerWidth<768)
setupevents();
else unsetevents();
}
window.onresize();
loadTheme();
_decryptonload();
}
</script>
<style>
frac{
text-indent:0;
display:inline-block;
font-size:50%;
text-align:center;
position:relative;
top:4px;
}
frac>sup{
display:block;
border-bottom:1px solid;
font:inherit;
}
frac>sub{
display:block;
font:inherit;
}
</style></head>
<body onload="ol()" style="overflow-x:hidden;">
<div id="panel" class="TText">
<ul id="panellist">
<li><a href="/"><h1>Chrisoft</h1></a></li>
<li><a href="/blog"><h2>Blog</h2></a></li>
<li><a href="#"><h3 id="title">ICPC类比赛中计算几何问题之「乱象」</h3></a></li>
<li><span>Tags</span>
<ul id="tagslist">
<li><a href="/blog/list/garbage/">garbage</a></li><li><a href="/blog/list/acmicpc/">acmicpc</a></li></ul>
</li>
<li id="tocouter" style="display: none;">
<span>Table of Contents</span>
<ul id="tocroot">
</ul>
</li>
<li style="margin-left:-0.5em"><a id="prevp" href="2018-04-17.html">Prev post</a></li>
<li style="margin-left:-0.5em"><a id="nextp" href="2018-05-03.html">Next post</a></li>
</ul>
</div>
<div id="content">
<h2 id="titleh" class="TText" style="font-wight:normal;">ICPC类比赛中计算几何问题之「乱象」</h2>
<div id="datetags" class="TText" style="margin-bottom:1em;">2018-04-22<br>#garbage #acmicpc</div>
<hr><div id="article" class="TText">
<article>
<p>
虽然我还从未在博客里面写过一篇仅与ACM/ICPC相关的文章，但是今天情况发生了改变……
</p>
<p>
今天打某神奇的「2018 ACM-ICPC 中国大学生程序设计竞赛暨丝绸之路程序设计竞赛」时，
遇到如下一题：
</p>
<blockquote>
在三维空间内给出一个平面和N个点，在给定平面内移动的速度为v<sub>2</sub>，在其余位置移动速度为v<sub>1</sub>，
求按一定顺序走遍N个点并回到起点的最短所需时间。
</blockquote>
<p>
当然原题面大约是六级不到500的人写的，所以猜题意用了不少时间。但是摸清题意之后，
不就是计算几何套裸的TSP吗……于是让队友先写好TSP模板然后我去推计算几何的部分了。
</p>
<p>
一开始非常智障地以为直接把点在平面上的投影点当落脚点就可以了，然而发现WA样例……
（虽然已经猜到了结果）于是假设每一端分别少走一段距离，如下图：
</p>
<div style="text-align:center;">
<img src="//filestorage.chrisoft.org/blog/img/180422-geomp.svg" alt="" width="80%" decoding="async">
</div>
<p>
此情形下每侧用时的变化量
Δt=<frac><sup>p</sup><sub>cosα×v<sub>1</sub></sub></frac>-<frac><sup>p×tanα</sup><sub>v<sub>2</sub></sub></frac>。
Δt'=p<frac><sup>sinα×v<sub>2</sub>-sin<sup>2</sup>α×v<sub>1</sub>-cos<sup>2</sup>α×v<sub>1</sub></sup><sub>cos<sup>2</sup>α×v<sub>1</sub>×v<sub>2</sub></sub></frac>
=p<frac><sup>sinα×v<sub>2</sub>-v<sub>1</sub></sup><sub>cos<sup>2</sup>α×v<sub>1</sub>×v<sub>2</sub></sub></frac>
所以极值在sinα=<frac><sup>v<sub>1</sub></sup><sub>v<sub>2</sub></sub></frac>时取得。<s>管它是什么极大值还是极小值反正</s>就用它好了。
</p>
<p>
然后因为懒得找模板于是手推了许久点在平面上的投影公式。打完之后发现……TLE！
然后发现队友写了递归的TSP……重写了非递归TSP之后秒过。<s>顺便还抢到了一血。</s>
如果一定要看我的辣鸡代码的话，<a href="//filestorage.chrisoft.org/blog/data/180422a.cpp">在这里</a>。
</p>
<p>
于是你就见识到了这道强行结合TSP的计算几何的奇葩题目。
<a id="n1" href="#note1" class="note">[1]</a>
17年北京区域赛时也有一个判断线段是否与三角形内部有交集×bfs的题目也是神坑。
</p>
<p>
不过高级别的比赛中的计算几何题目质量还是十分有保证的。像今年WF G题（疑似）用的Voronoi Diagram
<a id="n2" href="#note2" class="note">[2]</a>以及去年WF的A题。当然今年WF E题这种混合物理的题，
在官方发布数据之前我大概是过不了样例以外的任何测试点的（<a id="n3" href="#note3" class="note">[3]</a>
</p>
</article>
<!--
vim:syntax=html
-->
</div><br><hr>
<div class="TText" id="notediv" style="font-size:80%;"><span class="TText"><a id="note1" href="#n1">[1]</a>: 其实这套题目总体质量并不高……<br></span><span class="TText"><a id="note2" href="#n2">[2]</a>: 「疑似」是因为我还没写<br></span><span class="TText"><a id="note3" href="#n3">[3]</a>: 现在数据发布了，搞到数据立即发现起点坐标读反了以及多写了一对fabs。<s>面向数据编程真好</s>。<br></span></div>
<div id="insanch" style="height:3em;"></div>
<div id="footer" style="">
<div id="pagesw" class="TText" style="width:100%;height:0.5em;"></div>
<div style="text-align:center;" class="TText">
Proudly powered by SSBS <reduced style="font-size:70%;">(the static stupid blogging system)</reduced> 2.5
<br>
Content licensed under CC BY-SA 4.0. <span id="purgep" style="display:none;font-size:70%;">This page has passphrase(s) stored. Click <a href="javascript:_purgep()">here</a> to purge.</span>
</div>
</div>
<div id="cmdbuf" class="TText" style="transition:500ms;padding:1em;font-size:2em;color:white;position:absolute;background-color:rgba(0,0,0,0.6);left:50%;top:50%;transform:translate(-50%,-50%);pointer-events:none;opacity:0;">
</div>
</div>
<div id="decryptui" style="display:none;opacity:0;color:white;z-index:1000;position:fixed;left:0;top:0;width:100%;height:100%;background-color:rgba(0,0,0,0.4);transition:opacity 0.5s;">
<div id="decryptdlg" class="TText" style="padding:10px 20px;position:absolute;left:50%;top:50%;transform:translate(-50%,-50%);background-color:rgba(0,0,0,0.6);">
<div id="keyhint" style="margin-bottom:8px;"></div>
<div style="margin-bottom:8px;">Key: <input id="keyinp" type="text" style="color:#fff;"></div>
<div style="height:2.25em;">
<button id="btndecrypt" onclick="decryptor(decid,document.getElementById('keyinp').value);" style="position:absolute;left:20px;">Decrypt</button>
<button onclick="hidedecryptui();" style="position:absolute;right:20px;">Cancel</button>
</div>
</div>
</div></body></html>
|
