【20181102T2】飞越行星带【智商题+最小瓶颈路】 题面 【正解】 一眼不可做啊 ……相当于求路线上穿过的点最小距离最大 最小最大……二分啊 现在相当于给一个直径,要判断这个直径是否能从左边穿到右边 我们可以在距离不超过直径的点连一条边,(y=0)和(y=L)建虚点,然后判断他们是否连通,如果连通说明不能通过 复杂度(O(N^2 log(L/eps))) 实际上,这就是求两个虚点的最小瓶颈路的过程 也可以跑一遍最小生成树,在连通的时候输出加上的那条边 复杂度(O(N^2 log(N^2))),应该差不多 代码