O(n log n) 复杂度以内判断平面直角坐标系上的线段是否互不相交的办法

学术版

Shunpower @ 2022-10-06 12:33:20

RT,想写 SPJ,需要一个 O(n log n) 复杂度以内判断平面直角坐标系上的线段是否互不相交的办法。

只需要判断是不是互不相交,不需要其他的。

求一个简单的方法(除了扫描线我不知道别的办法了)。


by sdqe @ 2022-10-06 18:07:31

扫描线就很好写。只要维护前后驱,set就可以


|