Atcoder abc286

發表於 2023-01-28 更新於 2024-10-23 分類於 Atcoder ， ABC Disqus：文章字數： 316 所需閱讀時間 ≈ 1 分鐘

Ex(计算几何)

Ex - Don’t Swim

二维平面, 有N点的凸多边形C(逆时针给点),

以及两个点S和T(保证在多边形外部)

求从S到T不经过多边形内部的最短距离

n 1e5

所有坐标 [-1e9,1e9]

1024mb

看错题了

如果是凸包, 那就还好, 按S排个角度, 每次找下一个点和S哪个夹角更小, 就完了

问题是这里可能是奇怪的形状

   xxxx
S x   x
 x  xTx
    xxx

一个事实是, 如果从当前点能不穿过其它点到S,那么就直接走, 但是又该如何判断中间不被阻挡, 需要O(n)条边的判断?

那么其实任意两点都满足这个性质, 如果直接能到就直接走

最短路? 还是如何在非凸包判断不被阻断, 不会了

考虑 n个点包含S,T的凸包

如果S,T 在凸包上, 那么显然就是沿着凸包走

否则直接到达

VP 了一下, 91:51 做完了G

Ex 什么神奇的日本计算几何??

等等好像看错题了, C是凸包………………………………………………………………