2개의 댓글이 있습니다.
-
-
Taeyoon_Lee -
알고리즘 자체는 맞을 것 같은데요.. 저라면 이렇게 해볼 것 같습니다.
1) 랜덤 데이터 제네레이터를 만든다.(눈으로 확인할 수 있는 쉬운 데이터만 나오는..)
2) 몬테카를로로 풀어본다.
3) 1, 2를 이용해서 오차가 심한 데이터를 찾는다.
4) 찾은 데이터를 직접 그려보며 디버깅....:'(
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
restart
문제설명
N(<=8)개의 선분들이 주어지고, 각 선분 사이를 잇는 모든 선분을 그릴 때, 그 넓이를 구하는 문제입니다.
알고리즘 구상
선분들에서 2개를 골라 사각형을 만든다. 선택된 선분이 AB,CD라 할 때, - 선분 AC와 BD가 교차하면 사각형은 ABCD - 교차하지 않으면 ABDC
각 사각형의 모든 변을 기준으로 하여 모든 교차점을 찾는다.
교차점들의 x좌표를 set에 추가한다
2에서 만들어진 set의 인접요소들을 순회하면서 심슨법을 적용한다.
delta X = (X_{i+1} - X_{i} ) / 2
mid X = (X_{i+1} + X_{i} ) / 2
로 삼으면, 각 사각형들을 순회하면서 선분 (mid X, 0) - (mid X, INF)와의 교차점을 찾는다. 교차점의 y좌표는 심슨법에서 y_2가 된다. 이 교차점은 항상 2개이거나 0개이므로 큰쪽을 사각형 영역의 시작으로 삼고, 작은 쪽을 끝으로 삼는다.
교차점들을 y좌표가 큰순으로 순회하면서, 겹치는 사각형의 수를 세면서 칠해진 부분이 시작될 때 2 * delta X * y_2 를 더하고, 칠해진 부분이 끝날 때 2 * delta X * y_2 를 빼준다.
코딩
(알고리즘 문제 해결 전략의 기하라이브러리 사용)
기하는 디버그가 너무 어려워요ㅜㅜ.......
10년 전