algospot.com :: 질문과 답변: sum of area 문제에 대해서

sum of area 문제에 대해서

YiMaeTal

많은 댓글 부탁드립니다 :)

7년 전 link
일루

https://www.quora.com/What-is-coordinate-compression 같은것을 알아보세요. O(1)은 힘들 것 같습니다.

7년 전 link
YiMaeTal

@일루 역시 조건을 줘서 그냥 노가다로 하는 방법말고는 O(1) 힘든가요

7년 전 link
일루

n이 커지면 노가다로 해도 O(1) 이 아니겠죠...

7년 전 link
YiMaeTal

@일루 아 제 문제는 두개의 사각형이었어요.. ㅎㅎㅎ 당연 저문제에서는 O(n) 이죠 ㅎㅎ:)

7년 전 link
kriii

어떻게 O(n)으로 할 수 있는지 잘 모르겠네요.
두 직시각형은 각 차원에 대해 따로 보시면 비교적 깔끔하게 됩니다.

7년 전 link
kiyomi

@YiMae Tal 저 죄송한데 Graph Connectivity소스좀 받을수있을까요?

7년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

두개의 랜덤 사각형의 넓이를 구하는 문제인데
저는 문제를 풀때 사각형의 양 꼭지점의 위치를 가지고 네 좌표를 비교해가며 더하고 마지막에 교차하는부분이 있다면 그부분을 빼는식으로 문제를 풀었었습니다.
이게 너무 노가다식으로 푼거같아서 여러분의 의견을 듣고싶은데요

예를들어 이런 문제라고 한다면 (저는 사각형 두개의 좌표 8개를 받아서 푸는 문제였지만)
어떤식으로 다가가실지 궁금합니다.

시간복잡도의 경우 O(1) 을 지키면서 풀었으면합니다.

감사합니다^_^

7년 전