11개의 댓글이 있습니다.
-
-
wookayin -
- n : 50,000 (n^2 gg), k (영역의 수) : 1,000,000간단히 생각해봤는데 제가 떠올린 방법의 기본 idea는 x방향으로 플레인 스위핑을 하면서 y축에 평행한 segment [y1, y2] 하나가 그려질 때 새로운 영역이 생기고, 하나가 빠질 때 그 영역이 끝난다는 식으로 영역들을 maintain 하는데 얘네들이 하나의 영역으로 합쳐진다는 걸(?) Union and Find 와 유사한 방식으로 관리한다...는 느낌입니다.n^2 는 그럭저럭 짤 수 있겠지만 n lgn 은 어렵죠. 따라서 Segment Tree 나 Interval Tree 를 써서 해결할 수 있을 듯 합니다. 이게 k가 n^2 가 아니고 백만정도기 때문에 가능한 풀이인 것 같은데.. (머릿속으로만ㅁㄴㅇㄹ) 시험기간이니(?) 시험이 끝난후에 자세하게 풀어봐야겠네요 ㅎㅎ
14년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
hyida
n개 사각형의 좌표가 주어지는데 이 때 사각형이 겹쳐서생기는 모든 다각형의 개수를 구하고 다각형들의 넓이 중 가장 큰 것의 넓이를 구하는 문제입니다..
이 때 생기는 다각형의 개수는 1,000,000개 이하이고 n은 50000 이하라고 주어집니다.. n개의 사각형은 x축,y축에 평행합니다..
n^2 플레인스위핑을 인덱스트리 사용해서 n lg n만드는식인거 같은데
어떤식으로 플레인스위핑 해야될지 잘 모르겠네요..
도와주시면 감사하겟습니다..ㅜㅜ
14년 전