whgusfud   8년 전

signed area를 이용하면 선분들의 교차여부를 알 수 있다고 합니다.

그래서 아래와같이 코드를 짰습니다.

선분을 입력할 때마다, 그 전에 입력한 선분들과 교차여부를 체크합니다.

O(n^2)의 시간복잡도를 지녔습니다.

일단, int형이라 overflow가 나겠지만....그전에 시간초과가 일어납니다 ㅠㅜ

어떤 알고리즘이나 수학적 이론을 사용해야 풀리나요?

portableangel   8년 전

https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottm...

참고가 될듯 한 자료입니다

whgusfud   8년 전

감사합니다~ O((N+K)lgN) 알고리즘(K는 교점개수) 이군요.

아마 해답이 될 거 같습니다.

댓글을 작성하려면 로그인해야 합니다.