7개의 댓글이 있습니다.
-
-
Taeyoon_Lee -
치킨집은 제일 먼 점의 거리가 최소가 되는 점을 찾는 문제이고,
거리의 합이 최소가 되도록 하는 문제는http://plg1.cs.uwaterloo.ca/~acm00/020126/E.html
요건 것 같습니다.
답은 http://plg1.cs.uwaterloo.ca/~acm00/020126/data/E.c
이겁니다. 2분 검색 비슷하게 하네요.
(확실히 최적해를 구할지는 약간 의문이 가지만..)
16년 전 link
-
-
-
Taeyoon_Lee -
=_= 제가 아는 한 없습니다..맨하탄 distance로 계산한다면 있습니다..;;
직선 거리로 계산하는 경우, O(1) 솔루션은 본 적이 없습니다.
16년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
soyoja
친구가 갑자기 물어본 질문인데.. 좋은 방법이 생각나지 않네요. ;)
2차원 좌표상에 임의의 좌표들이 다수 주어질 때, 이 점들간의 대표점 ( 대표점은
주어진 좌표들간의 거리의 합이 최소가 되는 지점을 의미하며, 주어진 좌표중에서
찾는것이 아니고 거리의 합이 최소가되는 새로운 좌표를 찾는다는 의미입니다.) 을
찾는 좋은 방법 없을까요? 알고리즘이 존재하는 것 같던데 어떤 알고리즘을 사용하면
좋을지도 알려주시면 감사하겠습니다.
그냥 단순히 점들간의 평균으로 구해서는 안되더군요.
예) (0,0) (10,0) (10,1)
ps) ICPC 인터넷 예선에 나온 치킨집 문제가 이러한 유형의 3차원 버전인듯 한데
어떤 원리로 푸는지 아직 이해를 못했습니다. ^^;
16년 전