简述
一般赛场上遇上计算几何的题一般都不难,而碰上了没学过就直接爆零。为了避免这样的情况,我决定好好学一遍计算几何的一些东西。
结果是学了一遍照样爆零。
这道题作为偏序题还是很有意思的,第一次碰到「二维偏序」。
先考虑偏序条件,设圆原点在 \((a, b)\),现在有一个点 \((x, y)\),如果这个点被覆盖:
\[ (x – a)^2 + (y – b)^2 \leq a^2 + b^2 \]
直接做不太好做,很懵逼。可以考虑枚举 CCP 得到的票数,然后再从各大党派中各抢一张票。如果不够抢就直接抢最小的票。这样取 min 即可。
做起来很舒适的一套题。
这道题乍一看不是很能做,因为摆放状态很多。然而,计算机科学这种东西解决不了问题的时候不讲究正解,只讲究近似。所以,我们可以枚举一个旋转角 \(\theta\) 来决定最终摆放的形态。枚举之后就可以直接二分费用并建边做二分图。
在纪中,不铺好蚊帐就等着第二天比赛 GG。
kal0rona