<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</title>
<script type="text/javascript" src="/panel.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();
_decryptonload();
}
function loadTheme(){
var thm=document.cookie.replace(new RegExp("(?:(?:^|.*;\\s*)thm\\s*\\=\\s*([^;]*).*$)|^.*$"),"$1");
if(thm.length<2||'0123z'.indexOf(thm[0])==-1||'abz'.indexOf(thm[1])==-1)thm='zz';
var ent="";
var d=new Date();
if(thm[0]=='z')
{
var m=d.getMonth()+1;
if(m>=3&&m<6)thm='0'+thm[1];
else if(m>=6&&m<9)thm='1'+thm[1];
else if(m>=9&&m<12)thm='2'+thm[1];
else thm='3'+thm[1];
}
if(thm[1]=='z')
{if(d.getHours()>=18||d.getHours()<6)thm=thm[0]+'b';else thm=thm[0]+'a';}
ent=`theme${thm}`;
var R=new RegExp('theme[0-4][ab]');
for(var i=0;i<document.styleSheets.length;++i)
{
if(R.exec(document.styleSheets[i].ownerNode.id)!==null&&document.styleSheets[i].ownerNode.id!=ent)
document.styleSheets[i].disabled=true;
else document.styleSheets[i].disabled=false;
}
var thmcolor="";
switch(thm[0])
{
case '0':thmcolor=thm[1]=='a'?'#f59dda':'#2f0933';break;
case '1':thmcolor=thm[1]=='a'?'#9df59d':'#090933';break;
case '2':thmcolor=thm[1]=='a'?'#edb47b':'#1f1205';break;
case '3':thmcolor=thm[1]=='a'?'#a0cdfa':'#051933';break;
}
document.querySelector("meta[name=theme-color]").setAttribute('content',thmcolor);
}
loadTheme();
</script>
</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">
<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>
<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>