1266번 - 일어나!
signed area를 이용하면 선분들의 교차여부를 알 수 있다고 합니다.
그래서 아래와같이 코드를 짰습니다.
선분을 입력할 때마다, 그 전에 입력한 선분들과 교차여부를 체크합니다.
O(n^2)의 시간복잡도를 지녔습니다.
일단, int형이라 overflow가 나겠지만....그전에 시간초과가 일어납니다 ㅠㅜ
어떤 알고리즘이나 수학적 이론을 사용해야 풀리나요?
https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottm...
참고가 될듯 한 자료입니다
감사합니다~ O((N+K)lgN) 알고리즘(K는 교점개수) 이군요.
아마 해답이 될 거 같습니다.
댓글을 작성하려면 로그인해야 합니다.
whgusfud 8년 전
signed area를 이용하면 선분들의 교차여부를 알 수 있다고 합니다.
그래서 아래와같이 코드를 짰습니다.
선분을 입력할 때마다, 그 전에 입력한 선분들과 교차여부를 체크합니다.
O(n^2)의 시간복잡도를 지녔습니다.
일단, int형이라 overflow가 나겠지만....그전에 시간초과가 일어납니다 ㅠㅜ
어떤 알고리즘이나 수학적 이론을 사용해야 풀리나요?