【正解】
一眼不可做啊
……相当于求路线上穿过的点最小距离最大
最小最大……二分啊
现在相当于给一个直径,要判断这个直径是否能从左边穿到右边
我们可以在距离不超过直径的点连一条边,\(y=0\)和\(y=L\)建虚点,然后判断他们是否连通,如果连通说明不能通过
复杂度\(O(N^2 log(L/eps))\)
实际上,这就是求两个虚点的最小瓶颈路的过程
也可以跑一遍最小生成树,在连通的时候输出加上的那条边
复杂度\(O(N^2 log(N^2))\),应该差不多
本文共 282 字,大约阅读时间需要 1 分钟。
【正解】
一眼不可做啊
……相当于求路线上穿过的点最小距离最大
最小最大……二分啊
现在相当于给一个直径,要判断这个直径是否能从左边穿到右边
我们可以在距离不超过直径的点连一条边,\(y=0\)和\(y=L\)建虚点,然后判断他们是否连通,如果连通说明不能通过
复杂度\(O(N^2 log(L/eps))\)
实际上,这就是求两个虚点的最小瓶颈路的过程
也可以跑一遍最小生成树,在连通的时候输出加上的那条边
复杂度\(O(N^2 log(N^2))\),应该差不多
转载于:https://www.cnblogs.com/lstoi/p/9896784.html