SCPC 2017 본선 2번 풀이. Bridge

문제 설명(요약)

평면 위에 볼록다각형 모양의 두 섬 A와 B가 있다. A와 B는 서로 교차하지 않는다. A와 B 사이에 다리를 놓으려고 하는데, 다리 건설 비용을 최소화하기 위해 다리의 길이를 최소화하려고 한다.다리의 A쪽 끝점 P와 B쪽 끝점 Q에 대해, P는 A의 내부나 경계에, Q는 B나 내부의 경계에 위치해야 한다.

다리(선분 PQ)의 길이를 최소화하는 점 P와 Q에 대해, 그 길이를 구하여라.

제약 조건: A, B의 꼭짓점 수 N, M은 각각 200,000 이하

* 부분문제 1 (82점): N, M <= 1,000

* 부분문제 2 (126점): N, M <= 50,000

* 부분문제 3 (92점): N, M <= 200,000

실행 조건: 테스트 케이스 30개 총합의 실행시간이 3초 이하, 메모리 총합 256MB 이하

부분문제 1 풀이

최적해에서 다리의 양쪽 끝점은 반드시 각각 A, B의 경계에 위치한다. 만약 그렇지 않은 최적해 S가 있다면 해당 다리와 A, B의 경계가 만나는 두 점을 잡아 S보다 더 나은 최적해를 만들 수 있어 모순이기 때문이다.

따라서 P는 A의 경계에, Q는 B의 경계에 위치하는 것으로 간주하고 이들 경계에서만 점을 움직여도 된다. 그러면 P는 A의 N개의 선분 중 하나 위에, Q는 B의 M개의 선분 중 하나 위에 있으므로 N x M개의 선분 조합에 대해 해당 선분 조합을 택할 때 P와 Q 사이의 최소거리를 모두 계산해 최솟값을 취하면 된다. 두 선분을 연결하는 최소 거리 선분의 길이는 O(1)에 계산할 수 있으므로, 전체 시간복잡도는 O(NM)이다. 따라서 N, M <= 1,000인 부분문제 1은 해결할 수 있다.

부분문제 2 풀이

P점을 고정하고 Q점을 이동하는 경우 선분 PQ의 길이 변화를 생각해보자. Q가 볼록다각형 위를 움직이므로, 선분 PQ의 길이 함수는 최적점 Q_opt 근방에서 아래로 볼록하다. 따라서 parametric search를 생각할 수 있다. 하지만 전체 영역에서 아래로 볼록한 것은 아니다. P에서 먼 부분에서는 아래로 볼록하지 않을 수 있다. 그러면 어떻게 해야 하는가? 자세한 내용은 복잡하므로 Jacob T. Schwartz의 논문인 FINDING THE MINIMUM DISTANCE BETWEEN TWO CONVEX POLYGON (1981)을 참조하자. O(lg N * lg M) 내에 해결하는 방법이 제시되어 있다. 하지만 읽어보면 프로그래밍 대회에서 사용하기에는 좀 복잡한 감이 없지 않은 알고리즘이다.

그보다 단순하게 해결할 수는 없을까? 어떤 최적해의 양 끝점 P와 Q에 대해, 항상 P와 Q를 각각 지나는 서로 평행한 두 접선 L_P와 L_Q를 그을 수 있다. 왜냐고? P와 Q를 각각 지나고 PQ에 수직인 두 직선을 택하면 이 조건을 만족하기 때문이다. 만약 이렇게 접선을 그었을 때 L_P가 A와 P 근방에서 다시 만난다면 P점의 최적성에 모순이고, P에서 떨어진 부분에서 다시 만난다면 다각형 A의 볼록성에 모순이기 때문이다. L_Q에 대해서도 동일한 논리가 적용된다.

따라서 모든 가능한 접선 기울기를 시도해보면서 L_P와 L_Q를 한 바퀴 돌리면 된다. 그러면 반드시 하나 이상의 최적해를 고려하며 지나가게 된다. 이때 정해진 기울기 값을 갖는 접선은 다각형의 양쪽 끝 중 하나에 있을 수 있으므로 두 가지가 존재하므로 A와 B에 대해 합하면 총 네 가지를 고려해야 한다.

그런데 연속으로 돌리는 것은 구현이 불가능하므로 어떤 몇 개의 유한한 기울기들만을 고려하고 싶다. 어떻게 해야 할까? 잘 생각해보면, 최적해는 반드시 (A의 점, B의 선분) 또는 (B의 점, A의 선분) 간의 거리 중에 존재한다. 따라서 존재하는 모든 선분의 기울기를 시도해보면 충분하다. 그러므로 Rotating Calipers 알고리즘을 적용하는 것이 정당하다. 물론 약간의 변형이 들어간다. 원래의 Rotating Calipers 알고리즘은 하나의 볼록다각형에 대해 수행하지만, 지금은 두 개의 볼록다각형 A와 B에 대해 병렬적으로 수행하되 하나의 스텝은 두 개의 볼록다각형에서 회전할 수 있는 각도 중 작은 값을 택하여 매 스텝을 진행하여야 한다. 시간복잡도는 당연히 O(N+M)이 나온다. 대충 구현하면 부분문제 2를 통과하지만, 부분문제 3은 Fast I/O를 쓰지 않으면 통과하지 못할 수 있다. (입력 크기가 400,000개의 정수이므로 입력을 받는 데만 0.7초 가량이 소요되기 때문)

부분문제 3 풀이

Rotating Calipers는 하나의 접선이 한 바퀴를 돌 때까지 실행할 필요가 없다. 왜냐면 접선을 두 개 돌리기 때문이다. 따라서 하나의 접선은 반 바퀴만 돌아도 충분하다. 각각의 Caliper가 반 바퀴를 최초로 돌았을 때 카운트를 하고, 모든 Caliper가 반 바퀴를 돌았다면 종료하는 방식을 사용하면 시간을 거의 1/2로 줄일 수 있다. 그러면 Fast I/O 없이도 충분히 제한시간 내에 통과할 수 있다.

* 여담: 처음 풀었을 때는 볼록성에 착안하여 다각형의 고리를 자른 후 삼분탐색을 시도했었고, 온라인에서 만점도 나왔다. 함수로는 선분-선분 거리를 이용해 O(NM)개의 값이 존재하는 함수를 사용했었다. 한 번 적용하면 O(N lg M), 두 번 적용하면 O(lg N lg M)이 된다. 하지만 이 논리에는 반례가 존재한다. 하나의 선분을 고정했을 때 선분-선분 거리 함수는 증가함수와 감소함수를 이어붙인 형태가 아니다. 미세한 fluctuation이 있을 수 있다. 다만 온라인의 데이터는 이런 경우를 커버하지 못하는 것 같다. Codeground는 데이터가 너무 약하다.

보충 설명

* 두 선분을 연결하는 최소 거리 선분의 길이를 계산하는 방법: 두 선분을 매개화 형태로 표현하여 P + tu, Q + sv (0 <= t,s <= 1)이라고 하자. 그러면 이는 t, s를 매개로 하는 평행사변형으로, 한 꼭짓점이 P - Q이고, 그로부터 뻗어나가는 두 변의 벡터가 각각 u와 -v이다. 두 점 사이의 거리는 ||P + tu - Q - sv||로, 원점에서 평행사변형 위의 한 점까지의 거리에 해당한다. 이때 평행사변형이 원점을 포함하지 않으므로(두 선분이 만나지 않기 때문), 최단거리는 평행사변형의 경계 위에 있다. 경계는 네 선분으로 구성되므로, 각각의 선분에 대해 원점과의 최단거리를 계산하여 그 중 최솟값을 취하면 된다.

하나의 선분과 원점과의 최단거리는, 원점에서 선분(을 포함하는 직선)에 수선의 발을 내렸을 때 해당 선분에 포함되면 그 점이 최단거리점이고, 그렇지 않으면 양 끝점 중 하나가 최단거리다. 수선의 발이 포함되는지 여부는 선분의 매개화 형태 A + pB에 대하여 정사영을 내렸을 때의 p값이 0 이상 1 이하인지를 보면 된다. 이는 <A + pB, B> = 0에서 p = -<A,B>/<B,B>로 구할 수 있다.