쉬운 문제인듯 한데 풀이를 잘 모르겠네요.
문제)
좌표상에 n개의 점들이 주어집니다. (n<=5000)
이 점들을 대각선의 길이가 k인 D-사각형 1개로 최대한 많이 덮어야 합니다. (0 <= x,y좌표 <= 2^31-1인 정수, k는 2^31-1이하인 짝수)
예를 들어 아래 그림에서 k=4인 경우 왼쪽 D-사각형은 5개의 점을, 오른쪽 D-사각형은 3개의 점을 덮습니다.
가장 많은 점을 포함하는 D-사각형의 중심 좌표와 포함하는 점의 수를 구합니다. ( 5,4 와 5개가 되겠죠..)
45도로 돌려서 할려면 좀 복잡할거 같은데.
그렇게 안하고 n^2으로 가능하다고 들었는데 어떻게 할 수 있을까요?
가능성이 있는 정사각형의 위치를 추리면 될거같은데 그렇게 하면 너무 커질거같고...;;
도와주세요~
45도 돌려서 생각하는 것도 별로 어렵지 않은데.. ^^; 그쪽이 훨씬 코딩하기 쉬울 겁니다. 45도 돌린 뒤, 너비 x 인 세로 스트립으로 평면을 스위핑합니다. 스트립에 포함된 점들의 y좌표를 multiset 에 넣어 두면 되겠죠. 그리고 나면 또 O(n) 세로 스위핑을 하면 됩니다. O(n(lgn + n)) = O(n^2).
근데 더 쉬운 방법이 있으려나요? ㅎ_ㅎ
CYPark
쉬운 문제인듯 한데 풀이를 잘 모르겠네요.
문제)
좌표상에 n개의 점들이 주어집니다. (n<=5000)
이 점들을 대각선의 길이가 k인 D-사각형 1개로 최대한 많이 덮어야 합니다. (0 <= x,y좌표 <= 2^31-1인 정수, k는 2^31-1이하인 짝수)
예를 들어 아래 그림에서 k=4인 경우 왼쪽 D-사각형은 5개의 점을, 오른쪽 D-사각형은 3개의 점을 덮습니다.
가장 많은 점을 포함하는 D-사각형의 중심 좌표와 포함하는 점의 수를 구합니다. ( 5,4 와 5개가 되겠죠..)
45도로 돌려서 할려면 좀 복잡할거 같은데.
그렇게 안하고 n^2으로 가능하다고 들었는데 어떻게 할 수 있을까요?
가능성이 있는 정사각형의 위치를 추리면 될거같은데 그렇게 하면 너무 커질거같고...;;
도와주세요~
15년 전