Shunpower @ 2022-10-06 12:33:20
RT,想写 SPJ,需要一个 O(n log n) 复杂度以内判断平面直角坐标系上的线段是否互不相交的办法。
只需要判断是不是互不相交,不需要其他的。
求一个简单的方法(除了扫描线我不知道别的办法了)。
by sdqe @ 2022-10-06 18:07:31
扫描线就很好写。只要维护前后驱,set就可以