2개의 댓글이 있습니다.
-
-
restart -
한 점에 대해서 각각 P, Q로 이어지는 직선이 평면을 4분할한다는 점을 이용하면 분할정복으로도 풀 수 있으나 정신건강에 좋지 않구요..ㅠㅠ inversion개념을 이해하시면 쉽게 풀립니다.
http://www.geeksforgeeks.org/counting-inversions/ 를 참고하세요..
9년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
sw2o15
https://algospot.com/judge/problem/read/ANNIETIBBER#
ANNIETIBBER 문제에 대한 질문입니다.
기울기 판별을 이용해서 두 점을 비교하고 해당하는 점의 갯수를
카운팅 하는 방식으로 코딩을 한 결과 시간 초과가 발생합니다.
시간복잡도를 계산해보니 O(n^2) 이 나오더라구요
그래서 분할 정복을 사용해서 시간복잡도가
nlogn인 코드를 짜려고 하는데
아무리 생각해도 문제를 분할하는데 좋은 아이디어가 떠오르지 않습니다.
그래서 문제를 분할하는 방법에 대한 힌트를 얻고 싶습니다.
혹시 접근방법이 divide and conquer이 아니라면 그것에 관한
코멘트를 주셔도 감사하겠습니다.
9년 전