10개의 댓글이 있습니다.
-
-
김민현 -
문제가 잘 이해가 안가요.
"So the two groups agreed to
choose one island each, and then build each of the group’s main facilities on them, and split the region;
every point in this region will belong to the nearer base."
Split 을 어떻게 하는지에 대한 설명이 이문장인것 같은데,
2개 섬을 각각 선택한다음에 영역을 나누고, 그 영역의 모든 점은 더 가까운 base 쪽에 속하게 된다... 라는 뜻인데.
여기서 "모든 점(every point)" 이라는 것이 volcanic island들이 아니고, 그냥 임의의 모든 좌표점들을 말하는 건가요?
16년 전 link
-
-
-
김민현 -
네..암튼 저는 섬에 자원이 있으니까 섬에대한 소유권에 계속 집착이 가서 point 를 섬으로 밖에 못보는 결과를 낳은 것 같아요. clar 를 하긴 했는데;; 같은 거리에 있는 섬은 누구 꺼냐고.. 그 섬은 반드시 split 선이 지나게 되는거냐고 물었었는데, 그런건 아무 상관도 없다고 하더라구요.... 그래서.. 아 이해가 안된다 하면서.. every point 가 섬이 아닐꺼라는 생각은 아예 못하고 제 방식대로 생각하면 예제도 안나오기 때문에... 딴문제 풀었지요..ㅠㅠ 사실 쉬운거랑 어려운거랑 너무 확 격차가 있는것 같아요. 중간 레벨(쉬운 SRM 500 정도 수준에 약간의 성의 코딩 정도 수준?)이 좀 더 있었으면 해요. 저같은 하수는 초반에 좀 풀고 나니 남은 시간동안 GG ㅠㅠ.
16년 전 link
-
-
-
Taeyoon_Lee -
제가 가진 기하 라이브러리를 총동원하고도 주석포함 120줄을 짰네요..
사실 마지막에 Yes받은 답도 맞을 거라고는 생각 못하고,
"되면 좋고, 안되면 말고"라는 생각으로 남은 문제에 집중했는데
운좋게도 맞았네요ㅎㅎ
(No - Wrong Answer 뜨는 순간에 심장이 멎는 듯 했지만..)
16년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Being
악랄한 기하 3종세트에 속하는 문제로, 지난 모의고사에 쓰이지 않아 이번에 사용 된 두 문제 중 하나입니다. 나머지 한 문제는 Triangle Intersection이라고 역시 더러운 문제 하나 있습니다 (..)
일단, 어떤 facility points들을 공간에 찍어놓고 임의의 공간상의 점을 가장 가까운 facility point에 속하게 하여 그린 그림이 voronoi diagram입니다. voronoi diagram은 이미 아시는 분도 계시겠지만 일반적인 형태에서는 그닥 할 짓이 못 됩니다.
문제에서 주어진 조건과 같은 형태의 voronoi diagram은 L1-metric voronoi diagram이라고 합니다. Ln은 거리를 (|dx|^n + |dy|^n)^(1/n) 으로 정의하는 것입니다. L_inf는 max(dx, dy)가 되구요.
이 문제에서는 점이 두 개 뿐이기 때문에, 그들 사이의 일종의 이등분선을 찾아 그으면 됩니다. 이 이등분선의 모양은 일반적으로 이렇게 됩니다. (클릭해서 확대하세요)
이 이등분선의 식을 잘 구해 교점을 구하면 되는 문제입니다. 대강 두 점을 (a, b), (c, d) a <= c 라 하면,
i) b > d
ii) b < d
iii) b = d
이런 식으로 나누어서 식을 그려볼 수도 있겠고요, |c - a|와 |b - d| 사이의 대소 관계에 따라서 x = c 꼴의 직선들이 달릴지, y = c 꼴의 직선들이 달릴지가 결정됩니다. 형태를 일반적으로 나타내기가 쉽지 않기 때문에 섬세한 구현이 필요합니다.
잘 하면 O(N M^2) 에 나올 수 있을 정도로 N과 M을 줄였는데, 사실 출제자는 O(M^2 lg N) 에 풀었습니다. 이렇게 줄이는 것은 어렵지 않으니 한번 고민해보세요. (거기에 무려 유리수까지...)
16년 전