2차원 좌표상의 점들에서 거리가 최소인 지점 찾기

  • soyoja
    soyoja

    친구가 갑자기 물어본 질문인데.. 좋은 방법이 생각나지 않네요. ;)
    2차원 좌표상에 임의의 좌표들이 다수 주어질 때, 이 점들간의 대표점 ( 대표점은
    주어진 좌표들간의 거리의 합이 최소가 되는 지점을 의미하며, 주어진 좌표중에서
    찾는것이 아니고 거리의 합이 최소가되는 새로운 좌표를 찾는다는 의미입니다.) 을
    찾는 좋은 방법 없을까요? 알고리즘이 존재하는 것 같던데 어떤 알고리즘을 사용하면
    좋을지도 알려주시면 감사하겠습니다.

    그냥 단순히 점들간의 평균으로 구해서는 안되더군요.
    예) (0,0) (10,0) (10,1)
    ps) ICPC 인터넷 예선에 나온 치킨집 문제가 이러한 유형의 3차원 버전인듯 한데
    어떤 원리로 푸는지 아직 이해를 못했습니다. ^^;

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    13년 전
7개의 댓글이 있습니다.
  • Taeyoon_Lee
    Taeyoon_Lee

    치킨집은 제일 먼 점의 거리가 최소가 되는 점을 찾는 문제이고,
    거리의 합이 최소가 되도록 하는 문제는

    http://plg1.cs.uwaterloo.ca/~acm00/020126/E.html
    요건 것 같습니다.
    답은 http://plg1.cs.uwaterloo.ca/~acm00/020126/data/E.c
    이겁니다. 2분 검색 비슷하게 하네요.
    (확실히 최적해를 구할지는 약간 의문이 가지만..)


    13년 전 link
  • soyoja
    soyoja

    이분검색 말고 수학공식 형태로 계산하는 방법이 있을까요??
    원래 질문자의 의도는 O(1) 형태의 공식으로 표현가능한 솔루션이 존재하는지 묻는 것 같습니다만..


    13년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    =_= 제가 아는 한 없습니다..맨하탄 distance로 계산한다면 있습니다..;;
    직선 거리로 계산하는 경우, O(1) 솔루션은 본 적이 없습니다.


    13년 전 link
  • JongMan
    JongMan

    요거는 로컬서치네요. 전에도 이런 스타일의 솔루션을 본 적이 있어요.
    closed form 솔루션은 있을지 자신이 잘.. -.-


    13년 전 link
  • lewha0
    lewha0

    이번 일본 대회 문제 아닌가요?


    13년 전 link
  • lewha0
    lewha0

    다시 보니까 전혀 다르네요;;


    13년 전 link
  • nocut98
    nocut98

    에.. 루트 구하는 문제랑 비슷해져 버렸네요.
    뭔가 이런 식은 초콤 상콤하지가 않다능(아 나이가 몇갠데 이런 말투를 ㅋㅋㅋ)


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