MMRECT2질문 (평면상 가까운 좌표 먼 좌표 찾기)

  • alg0643671
    alg0643671

    먼저 .가까운 사각형 찾는문제는 알겠습니다
    얼마전 질문한 closet pair 알고리즘과 비슷하게
    x좌표 솔트 후 분할정복 으로~!

    그런데 먼 두점은 어떻게 해야됄지 모르게네요
    dynamic 으로 해야 되는 것 같은데 ... 초보라서 감도 안오네요 ㅠㅠ..
    힌트좀 주세요 흑흑 어디 수도코드같은건 없을까요..?


    11년 전
6개의 댓글이 있습니다.
  • josh
    josh
    1. Farthest-point vorinoi diagram
    2. Convex hull + farthest pair problem on convex polygon
    3. simple O(N^2) algorithm

    11년 전 link
  • JongMan
    JongMan

    아.. 이 문제 풀려고 찾아보신 거였어요? 이 문제에서는 찾은 점으로 x,y축에 평행한 정사각형을 만들어야 하기 때문에 일반적인 가장 가까운 쌍-가장 먼 쌍과는 다른 방법으로 풀어야 합니다. 훨씬 간단한 방법이 있으니 찾아보세요~ ㅎㅎ

    아무 제약도 없이 그냥 좌표평면 위의 점들 중 가장 먼 두 점을 찾을 때는 위에서 josh님이 말씀하신 방법처럼 하시면 됩니다.


    11년 전 link
  • alg0643671
    alg0643671

    아항.. 먼 두점 찾는것도 알것같네요! 감사합니다
    근데 훠얼씬간단한방법이 있다니...후얼 궁금하네요 ㅎㅎ 일단 가까운점 먼점을 이용해서 풀어볼려구요 그담에 차자바야겠담


    11년 전 link
  • JongMan
    JongMan

    가장 먼 두 점을 찾아냈다 해도 이 점들을 이용해서 정사각형을 만들 수 있다는 보장이 없기 때문에 이 문제를 풀기는 어렵습니다. ^^;


    11년 전 link
  • alg0643671
    alg0643671

    ㅋ헝 .. 그러네요 ㅠㅠ .. 흑흑 몇일째 하는데 풀질 못하네요 힌트좀부탁드려요 ㅎㅎ


    11년 전 link
  • hyunhwan
    hyunhwan

    임의의 가능한 두 점을 잡아보세요, 그리고 그 두 점이 만들고자 한 사각형의 왼쪽 위 오른쪽 아래 점이라고 생각해보세요.


    11년 전 link

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