쉬운 문제인듯 한데 잘 모르겠네요. 도와주세요.

  • CYPark
    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년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    45도 돌려서 생각하는 것도 별로 어렵지 않은데.. ^^; 그쪽이 훨씬 코딩하기 쉬울 겁니다. 45도 돌린 뒤, 너비 x 인 세로 스트립으로 평면을 스위핑합니다. 스트립에 포함된 점들의 y좌표를 multiset 에 넣어 두면 되겠죠. 그리고 나면 또 O(n) 세로 스위핑을 하면 됩니다. O(n(lgn + n)) = O(n^2).
    근데 더 쉬운 방법이 있으려나요? ㅎ_ㅎ


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