口胡 LOJ2548 [JSOI2018 绝地反击]

传送门

题目大意

平面上有$n\le200$艘飞船,移动到圆心为圆点,$R$为半径的一个圆上,并且要求相邻飞船距离相等(即组成正多边形)。

一艘飞船的速度为$1/s$,飞船可以同时移动。

询问所有飞船就位的最小时间。

解析

考虑二分答案,那就$n$艘飞船就变成了$n$个圆,和目标圆有一段圆弧的交(大概是这个意思,可能是整个圆,也可能为空)。然后每个圆弧,对应着弧度制的一段区间。

考虑如果方案合法,我们一定可以旋转整个多边形,使得多边形的某个顶点正好卡在某个区间的边界上。

然后就考虑加入一条边,我们要增广。

删掉一条边,如果这条边没有流的话,就直接把容量改成0。

如果有流的话,只涉及到三条边的流量,都修改就好。

然后再增广。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×