https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm
여기 읽어보면
left endpoint
right endpoint
crossing point 만날때마다 이벤트가 일어나는데
이때 point 바로 위 아래에 대해(crossing은 조금 다르긴하지만) intersection point를 계산하는 부분에서
위 아래 구할라면 tree의 원소들의 y좌표를 이벤트마다 업데이트 해줘야 하는거 아님? 깃헙찾아봐도 그렇게 구현되있던데
근데 그런식으로 구현하는거면 문제풀때 시간터질거같고 더 좋은방법없나
https://github.com/valenpe7/bentley-ottmann
이건 벤틀리 오트만 자바로 구현해놓은 주소