koosaga's profile image

koosaga

July 21, 2019 00:00

2019 한국정보올림피아드(KOI) 중/고등부 문제 풀이

중등부 1번. 신기한 수

Subtask 2 (100점)

숫자 $N$ 이 주어지면, 해당 수의 일의 자리에 적힌 수는 $N \mod 10$ 이 된다. 이후 숫자를 10으로 나눠주면, 십의 자리, 백의 자리… 에 있던 수들이 모두 일의 자리, 십의 자리로 움직인다. 고로, 이를 반복하면 $O(\log N)$ (입력에서는 최대 8번) 의 단순 연산으로 $N$의 자릿수 합을 알 수 있다. 어떠한 수 $A$ 가 어떠한 수 $B$ 로 나누어 떨어지는 것은, $A$ 를 $B$ 로 나눈 나머지가 0이라는 뜻이니, C++ 나머지 연산자를 사용하여 판별할 수 있다.

중등부 2번. 개구리 점프

Subtask 1 (19점)

어떠한 두 선분 $p, q$ 사이를 오갈 수 있다는 것은, 특정한 좌표 $x$ 가 존재해서, $p, q$ 의 $x$좌표 구간이 모두 $x$를 포함하고, $x$를 포함하며 $y$좌표가 $p, q$ 사이에 있는 다른 구간이 없다는 것을 뜻한다. 모든 $p, q$와 $[-1000, 1000]$ 구간에 있는 $x$를 다 시도해 보면 $2000 \times N^2$ 시간에 모든 쌍에 대해서 해당 정보를 구할 수 있다. 이제 오갈 수 있는 연결 관계를 그래프로 생각하면, 각 쿼리마다 적당한 그래프 탐색 알고리즘 (혹은 Floyd-Warshall) 로 문제를 해결할 수 있다.

Subtask 3 (100점)

사실, 어떠한 두 선분 $p, q$ 사이를 오갈 수 있다는 것은 두 선분의 $x$좌표 구간이 교집합을 가진다는 것과 동치이다. 즉, $y$ 좌표를 깡그리 무시해 줘도 상관이 없다. 이유는, 그 사이에 다른 구간들이 존재한다면, 그 구간들을 그냥 거쳐서 가도 상관이 없기 때문이다 (…)

두 구간 사이를 오갈 수 있는지는 아래 방법으로 판별 가능하다. 모든 구간을 시작점 순으로 정렬하여 순서대로 처리하고, Union-find 자료 구조를 사용하자. 정렬된 배열 상에서 인접한 두 구간이 교집합을 가진다면, Union-find에서 두 구간을 합쳐주고, 두 구간을 합집합으로 대체한다. 이를 시작점 순서대로 반복하면, Union-find 에 각 컴포넌트에 대한 연결 정보가 전부 저장되어 있으니, 두 점이 연결되어 있는지는 모두 빠른 시간에 판별할 수 있다. 시간 복잡도는 $O((N + Q) \log N)$ 이다.

중등부 3번. 드론

Subtask 3/4 (24점)

색에 따라서 드론의 위치가 유일하게 정해지기 때문에, 주어진 $T$ 개의 색은 드론이 방문해야 하는 $T$ 개의 좌표 위치에 정확히 대응한다. 고로, 시작점 -> 1번 위치 -> 2번 위치 -> … -> $T$ 번 위치 -> 도착점 순으로 순서대로 각 셀을 방문하는 최단 시간을 찾는 문제가 된다.

Subtask 3에서는 벽이 없기 때문에, 두 위치의 $X$ 좌표 차와 $Y$ 좌표 차의 합이 두 위치의 거리와 동일하다 (Manhattan Distance), 입력을 순서대로 받으면서 이 정보를 처리하면 된다. 시간 복잡도는 $O(N^2 + M + T)$ 이다.

Subtask 4에서는 벽이 있기 때문에, 두 위치의 거리를 계산하는 것이 위처럼 간단하지 않다. 이 때는 그래프를 도입해서 문제를 해결할 수 있다. 각 격자점을 정점, 인접한 격자점 사이를 오가는 것을 간선이라고 생각하면, 두 위치를 가장 빠르게 오가는 길은 그래프에서 두 정점의 최단 경로에 대응되니, 모든 인접한 쌍에 대한 최단경로를 더하는 식으로 문제의 답을 구할 수 있다. 그래프 입력이 귀찮게 주어지긴 하지만, 어쨌든 적당히 잘 처리하면 일반적인 adjacency list 형태로 저장해 줄 수 있다.

이를 단순하게 하면 $O(TN^2)$ 라서 시간 초과가 날 수 있으나, 우리가 계산해야 하는 최단 경로의 서로 다른 시작점은 많아야 $M+2$ 개이고, BFS 알고리즘은 고정된 시작점에 대해서 모든 도착점까지의 거리를 계산할 수 있다. 고로 $O(M)$ 번만의 BFS로 충분하다. 구현의 편의를 위해서 시작점과 도착점에 $N^2+1, N^2+2$ 이라는 색을 칠해주면 좋다. 시간 복잡도는 $O(MN^2 + T)$ 가 된다.

만점 풀이 (100점)

Subtask 4와의 차이는, 색이 고정된다고 위치가 고정되는 것이 아니라는 점이다. 하나의 색에 대해서도 여러 가지 위치가 있을 수 있고, 이 위치를 어떻게 하는 지에 따라서 거리가 달라진다. 고로 동적 계획법과 같은 방법으로 모든 위치를 시도해야 한다.

$DP[i][j]$ 를, $i$번 LED 타일을 $j$ 번 위치에 드론을 넣어서 밝혔을 때의 최소 시간으로 정의하자. 상태 전이는, $i-1$ 번 LED 타일을 채우기 위해서 드론을 넣은 위치 $k$ 를 모두 순회하면 가능하다. 두 위치에 대한 거리는, Subtask 3/4에서 했던 대로 $O(M)$ 번의 BFS를 통해서 전처리하면 $O(1)$ 시간에 계산할 수 있다.

고로, 한 항을 채우기 위해서 $O(M)$ 시간이 필요하고, 최종적으로 DP를 $O(TM^2)$ 시간에 계산해 줄 수 있다. 여전히 BFS가 필요하기 때문에, 시간 복잡도는 $O(MN^2 + TM^2)$ 가 된다.

중등부 4번. 물 채우기

Subtask 1 (7점)

왼쪽과 오른쪽이 모두 바닥에 닿아 있을 경우 답은 $(M - 2) \times $ (둘 중 작은 쪽 높이), 아닐 경우 답은 0이다.

Subtask 2 (25점)

가장 높은 덩어리를 기준으로 왼쪽에서는 물이 왼쪽으로 흐르고, 오른쪽에서는 물이 오른쪽으로 흐른다. 고로, 각 위치에 고인 물의 높이는 왼쪽에 있는 가장 높은 덩어리 (혹은 그 반대) 의 높이에 따라 좌우된다. 초기에 가장 높은 덩어리를 $O(M)$ 시간에 찾은 후, 덩어리를 기준으로 왼쪽 / 오른쪽으로 훑으면서 각 위치의 물의 높이를 계산해 주면 $O(M)$ 시간에 문제가 해결된다.

Subtask 4 (100점)

문제의 제약 조건 때문에 공중에 떠 있는 덩어리들은 바닥에 닿아 있는 덩어리와 완전히 독립적인 것이라고 생각할 수 있다. 고로 이를 최대한 따로 생각한다.

두 공중 덩어리가 인접한 열에 있고 교집합을 가지면, 두 덩어리가 “연결되어 있다” 라고 생각할 수 있다. 이렇게 연결된 공중 덩어리 컴포넌트들을 계산한다. 이러한 공중 덩어리 컴포넌트들은 위에서 물이 쌓이는 것을 방해할 수 있는 요인이 전혀 없기 때문에, Subtask 2와 같은 요령으로 공중 덩어리 컴포넌트에 고인 물의 양을 $O(M)$ 시간에 계산해 줄 수 있다.

이제, 바닥에 고인 물의 양을 계산해보자. 먼저, 공중 덩어리 컴포넌트가 없다고 생각하고 Subtask 2의 요령으로 물의 양을 계산해 줄 수 있다. 한편, 실제로는 공중 덩어리 컴포넌트 때문에 생각한 위치에 물이 고이지 않았을 수도 있어서, 예상과 다르게 고이지 않은 양이 얼마인지를 알아줘야 한다.

공중 덩어리 컴포넌트에 물이 쌓여 있지만, 어차피 이 물의 양은 앞에서 계산했고, 위에 쌓인 물이 빠지는 일도 없으니, 이 고인 물들을 그대로 덩어리라고 생각하고, 공중 덩어리 컴포넌트에 물이 전혀 쌓이지 않았다고 (그리고 쌓일 수도 없다고) 가정해 줄 수 있다. 이렇게 될 경우 공중 덩어리 컴포넌트는 단순히 물의 공간을 차지하는 장애물일 뿐이므로, 물이 있을 수 있는 위치에 공중 덩어리 컴포넌트가 어느 정도의 위치를 차지하고 있는지만 알면 된다. 이는 (물이 고인 구간 길이) - (물이 고인 구간과, 공중 덩어리 컴포넌트의 교집합 길이) 이니, 단순 계산으로 알아낼 수 있다. 시간 복잡도는 $O(M)$ 이다.

고등부 1번. 타일

타일 문제는 복잡한 알고리즘을 요구하지 않아서 풀이로 적을 내용은 길지 않으나, 구현 면에서 까다로운 점이 있는 문제이다. 고등부 1번을 풀지 못하였을 경우 다음과 같은 공부법을 추천한다. 고등부 1번 뿐만 아니라 어떠한 문제를 해결하더라도 이러한 방식으로 접근하는 것이 좋다.

• 1. 먼저 컴퓨터를 일절 사용하지 않고 펜과 종이만을 사용하여 적절한 수도코드(pseudo-code)로 코딩을 완료해 놓은 후,
• 1. 종이에 적힌 내용을 구현하고 정답 결과를 확인한 후, 틀렸을 경우 1번으로 반복
• 1. 맞았을 경우 다른 좋은 구현을 보고 차이점 분석

Subtask 1/2 (45점)

타일을 교체하는 선택지가 없기 때문에, 문제에서 주어진 입력 하에 차량이 도착점으로 움직일 수 있는 지를 판별하면 된다. 이는 시작점에서부터 타일에 표시된 방향을 따라서 차를 움직이고, 도착점에 성공적으로 도달했는지를 판별하는 식으로 가능하다. 가는 도중 길이 끊어지거나 도착지가 아닌 엉뚱한 곳에 도착하면 답이 아니다. 이 알고리즘은 $O(n^2)$ 이다.

Subtask 3/4 (100점)

각 위치에 대해서 5개의 서로 다른 타일 교체가 가능하고, 위치는 총 $n^2$ 개 있으니, 총 $5n^2$ 개의 타일 교체를 시도해 볼 수 있다. 타일을 교체한 후 경로가 있는지는, 서브태스크 1/2의 요령으로 하면 된다. $5n^2$ 번 $O(n^2)$ 연산을 수행하니 총 시간 복잡도 $O(n^4)$ 에 문제가 해결된다.

여담으로, 이 문제는 $O(n^2)$ 시간 복잡도에도 해결 가능하나, 별로 흥미롭거나 알 가치가 있는 풀이는 아니다.

고등부 2번. 괄호 문자열

Subtask 1 (17점)

$N \le 10$ 이기 때문에 펜과 종이만을 사용하여 여러 시행착오로 답을 찾은 후 이를 출력하는 프로그램을 작성하면 된다.

Subtask 2 (48점)

충분히 좋은 답에 대한 보상을 제공하니, Subtask 3을 풀 지식이 없다면 여기서 창의성을 발휘하면 된다. 다양한 전략이 존재한다.

• () 괄호를 $n$ 번 출력하면 0.29점을 받는다.
• 마찬가지로 () 괄호만을 사용하는데, $F(2n) = “(“ + F(n) + “)”$, $F(2n+1) = “()” + F(2n)$ 이라는 귀납적 식을 찾을 수 있다. 이는 $4 \log N$ 개의 괄호만을 사용하며, 40점 가량을 받는다.

이 외 백트래킹 등 다양한 전략이 존재한다.

Subtask 3 (100점)

괄호 문자열은 귀납적으로 정의되기 때문에 재귀적인 해결 방법이 유용하다. 이 문제에서는 괄호 문자열에 대한 Dynamic Programming을 사용하여 문제를 해결한다. $DP[i] = $ ($i$ 라는 답을 얻어낼 수 있는 최적의 문자열) 이라고 정의하자. 일반적인 DP와 다르게 최솟값이 문자열로 정의된다는 것이 특이한 점이지만, 큰 차이가 생기지는 않는다.

DP를 정의하면, 이제 문제에서 주어진 재귀적 정의를 그대로 풀어 쓰면 된다. 대략 다음과 같다:

• $i$ 가 2, 3, 5의 배수일 경우, 예를 들어 2의 배수일 경우, “(“ + $DP[i / 2]$ + “)” 가 가능한 답의 후보 중 하나이다.
• 모든 $1 \le j \le i - 1$ 에 대해서, $DP[j] + DP[i - j]$ 가 가능한 답의 후보 중 하나이다.

모든 가능한 후보 중 최솟값을 취하면 되는데, 두 문자열을 비교하는 규칙은 문제에 잘 써져 있으니, 이 규칙을 구현하여 최솟값을 취해 주면 된다. 이 방법대로 모든 $1 \le i \le 1000$ 에 대해 미리 전처리를 해 두고, 각 테스트 케이스마다 필요한 문자열을 출력해주면 된다.

위와 같이 구현을 한 후 로컬에서 테스트를 해 보면 시간 안에 잘 나오기 때문에 굳이 시간 복잡도를 증명할 필요는 없다. 하지만 어렵지 않게 상한을 증명할 수 있다. Subtask 2의 $4 \log N$ 길이의 전략이 존재하기 때문에, 답은 항상 $4 \log N$ 이하의 길이를 가지고, 고로 전처리 시간 복잡도는 $O(N^2 \log N)$ 가 되어 문제를 해결하기 충분하다.

여담으로, 이 문제 역시 $N \le 100000$ 이어도 해결 가능하나, 별로 흥미롭거나 알 가치가 있는 풀이는 아니다.

고등부 3번. 검은 돌

Subtask 1 (9점)

모든 정점 부분집합을 순회한 후, 해당 정점 부분집합이 이루는 그래프가

• 트리인지 (즉 연결되어 있는지)
• 돌을 몇 개 가지고 있는지

를 확인한다. 이 정보를 모두 취합하면 모든 $q = (i, j)$ 에 대한 답을 저장하는 2차원 행렬을 구할 수 있고, 모든 쿼리에 대해 출력해주면 된다. 정점 부분 집합의 개수가 $2^N$ 개이니, 시간 복잡도는 $O(2^N \times N + Q)$ 이다.

Subtask 2 (36점)

트리 DP를 사용하여 문제를 해결할 수 있다. (이 글에서는 트리에서 DP를 어떻게 하는지는 따로 소개하지 않겠다.) 우리가 관심있는 내용은 서브트리의 크기와 검은 돌의 개수이니, 이 인자들을 고려하여 다음과 같은 DP 점화식을 세울 수 있다.

$DP[v][i][j] = ($정점 $v$ 를 포함하는 서브트리 내에, $i$ 개의 정점을 가지고 $j$ 개의 정점에 검은 돌이 놓여 있는 서브트리가 존재하는가?)

일반성을 잃지 않고 입력이 이진 트리라고 가정하면 (이것이 왜 일반성을 잃지 않는지 모르겠다면 트리 DP에 대해서 공부하자.) 이 동적 계획법을 각 노드에 대해서 $O(sz(L)^2 \times sz(R)^2)$ 시간에 합쳐줄 수 있다. 결국 $O(N^5)$ 시간 복잡도 알고리즘이 유도되는데, 대부분의 경우에서 상수가 상당히 작다는 것을 알 수 있고, 고로 모든 $N \le 100$ 크기의 트리에서 잘 작동한다. 모든 $DP[v][i][j]$ 값을 알고 있다면 쿼리에 응답하는 것은 간단하다.

사실 본인은 $O(N^5)$ 과 $O(N^3)$ 사이의 복잡도를 가진 쉬운 풀이를 잘 모르기 때문에, 이에 대해 좋은 의견이 있다면 댓글로 적어주면 좋을 것 같다.

Subtask 3 (64점)

입력이 갑자기 커졌기 때문에, 위의 DP 테이블은 이제 잡을 수도 없다. 풀이 방향을 완전히 바꿔서 그리디로 접근하면 잘 풀리지 않으니, 위 DP를 최적화하는 방향으로 문제를 해결한다. 정확히는, 상태 전이를 최적화하는 것도 아니라, 상태의 개수 자체를 최적화하는 식으로 문제를 해결한다. 여기서, 다음과 같은 Lemma가 등장한다.

• Lemma. $DP[v][i][j]$ 가 참인 $i$ 는 연속된 구간을 이룬다. 즉, 어떠한 두 정수 $l, r$ 이 존재하여, $DP[v][l][j], DP[v][l+1][j], \cdots, DP[v][r][j]$ 만이 참이 된다.

• Rough Proof Sketch. 트리 정점 개수에 대한 귀납법을 사용하면 된다. $v$ 의 두 자식 노드 $p, q$ 에 대해 해당 성질이 성립한다면, $DP[p][][x], DP[q][][j - x]$ 를 AND로 묶어준 경우에 대해서도 해당 성질이 성립한다. 이제 $p$ 를 루트로 하고 $x$ 개의 노드를 포함하는 최소 서브트리와 $q$ 를 루트로 하고 $j-x$ 개의 노드를 포함하는 최대 서브트리를 생각해 보자. $p$ 에서 노드를 아무거나 빼면 $x-1$ 개의 노드를 포함하게 되며, $q$ 에서 노드를 아무거나 추가하면 $j-x+1$ 개의 노드를 포함하게 된다. 이는 $DP[p][][x], DP[q][][j - x]$ 를 AND로 묶어준 구간과 $DP[p][][x-1], DP[q][][j - x+1]$ 를 AND로 묶어준 구간이 교집합을 가짐을 뜻한다. 고로 둘의 합집합은 하나의 구간이 되고, 전체에 대해서도 성립한다.

이 점을 활용하면, DP에서 $i$ 라는 인자를 가지고 있을 필요가 없이, $i$ 의 가능한 최솟값과 최댓값을 반환하는 DP를 구현한 후, 나중에 각 $j$ 에 대해서 가능한 $i$ 의 범위를 저장해 놓으면 쿼리를 $O(1)$ 에 응답할 수 있다. DP 정의는 다음과 같이 바뀐다:

$DPmin[v][j] = ($정점 $v$ 를 포함하는 서브트리 내에, $j$ 개의 정점에 검은 돌이 놓여 있는 서브트리의 최소 크기는 무엇인가?)

$DPmax[v][j] = ($정점 $v$ 를 포함하는 서브트리 내에, $j$ 개의 정점에 검은 돌이 놓여 있는 서브트리의 최대 크기는 무엇인가?)

각 노드에 대해 $O(B^2)$ 시간에 합쳐주면 $O(NB^2)$ 시간에 문제가 해결된다.

Subtask 4 (100점)

위 DP를 구현할 때, 두 노드를 합쳐주는 가장 일반적인 방법은, 왼쪽 서브트리에서 $min(B, sz(L))$ 만큼의 크기들을 전부 순회해 보고, 오른쪽 서브트리에서 $min(B, sz(R))$ 만큼의 크기들을 전부 순회하는 것이다. 이를 합치면 각 노드에 대해 $min(B,\ sz(L)) \times min(B, sz(R))$ 만큼의 시간을 소모하게 될 것이다.

이러한 일반적인 방법으로 DP를 구현해 주면 놀랍게도 만점이 나온다. 그 이유는, 위 알고리즘의 시간 복잡도가 $O(NB)$ 이기 때문이다. 아래에 그 이유를 증명한다.

• Lemma. 이진 트리가 주어질 때, 각 노드에 대해서 $min(B,\ sz(L)) \times min(B, sz(R))$ 를 더한 값은 많아야 $O(NB)$ 이다.
• Proof. 더블 카운팅을 사용한다. $min(B, sz(L))$ 은 왼쪽 노드의 서브트리에 있는 수들 중 DFS preorder 번호가 가장 높은 $B$ 개의 정점의 수며, $min(B, sz(R))$ 은 오른쪽 노드에서 DFS preorder 번호가 가장 낮은 $B$ 개의 정점의 수이다. 이러한 두 정점 쌍의 개수는, DFS preorder 상 거리가 $2B$ 인 정점 쌍의 개수보다 작거나 같 다. 이는 $O(NB)$ 이다.

고로, $O(NB)$ 시간에 문제가 해결되고, $B \leq N$ 이니 $O(N^2)$ 에 문제가 해결된다. 여담으로, 똑같은 방식으로 사실 Subtask 2의 풀이가 $O(N^4)$ 라는 것을 증명할 수 있다.

고등부 4번. 고압선

Subtask 2 (35점)

최적해는 항상 다음 두 형태 중 하나이다:

• 입력으로 주어진 두 점 $p, q$ 에 대해서, $\overline{pq}$ 의 수직이등분선
• 입력으로 주어진 세 점 $p, q, r$ 에 대해서, $r$ 에서 $\overline{pq}$ 에 내린 수선의 수직이등분선

증명은 다음과 같다. 최적해의 길이를 $X$ 라고 하자. 각 점에서 반지름 $X$ 인 원을 그었을 때, 우리는 양 옆에 원을 끼면서 어떠한 원도 닿지 않는 직선을 찾아야 한다. 이 직선의 왼쪽과 오른쪽에는 적어도 하나의 원이 접해 있을 것이다 (그렇지 않다면 답을 늘릴 수 있다). 이 원을 $p, q$ 라 하자. 만약 $p, q$ 가 서로 닿아있는 원이라면 이는 첫번째 형태에 대응된다.

그렇지 않다면, 이 두 원에서 멀어지는 방향으로 직선을 회전하는 것을 시도할 수 있다. 만약 이 회전 시도가 성공한다면, 이는 최적해의 양 옆에 원이 접하지 않게 할 수 있다는 (고로 답을 늘릴 수 있다는) 뜻이므로 가정에 모순이다. 고로 $p, q$ 와 별개로, 회전을 못하게끔 직선에 접해있는 원이 하나 더 있음을 알 수 있다. 이 원을 $r$ 이라고 하면, 이제 이 경우는 두번째 형태에 대응된다.

이제 가능한 직선이 $O(N^3)$ 개이니, 이 후보들을 모두 시도해 보면 $O(N^4)$ 알고리즘이 된다.

Subtask 3 (44점)

증명을 제대로 이해했다면, 두 번째 형태에 대한 약간의 관찰로 시간 복잡도를 줄일 수 있다.

선분 $\overline{pq}$ 와 점 $r$ 을 고르고, $r$ 에서 $\overline{pq}$ 에 평행한 직선을 그었다고 하자. 만약 직선 $\overline{pq}$ 와 이 직선 사이 영역 (개구간과 같이, 해당 직선들은 포함하지 않는 영역을 생각하자) 에 점이 존재한다면, 이 선택은 올바른 선택이 될 수 없고, 그렇지 않을 경우에는 항상 ($\overline{pq}$ 와 $r$ 간의 거리) / 2 만큼의 답을 얻을 수 있다.

고로, 직선 $\overline{pq}$ 에 대해서, $ccw(p, q, r) > 0$ 인 점 중 $\overline{pq}$ 에 가장 가까운 점, $ccw(p, q, r) < 0$ 인 점 중 $\overline{pq}$ 에 가장 가까운 점, 이 두 후보만이 올바른 $r$ 의 후보가 된다. 또한, 이로 만든 직선에서 가장 가까운 점은 항상 $p, q, r$ 이니 단순히 수선의 길이를 2로 나눠주면 답을 찾을 수 있다. 이렇게 하면, 두 번째 케이스를 $\overline{pq}$ 당 $O(N)$ 에 처리할 수 있어서 $O(N^3)$ 알고리즘이 된다.

Subtask 4 (74점)

일단, 위 Subtask 3에서 썼던 아이디어를 그대로 사용하여서 첫 번째 형태도 단순화 할 수 있다. 선분 $\overline{pq}$ 의 수직이등분선에 평행하고, $p, q$ 를 각각 지나는 두 직선을 생각하자. 이 두 직선 사이의 (이번에도, 두 직선을 포함하지 않는) 영역에 점이 존재한다면, 이 선택은 올바른 선택이 아니고, 그렇지 않다면, ($\overline{pq}$ 의 길이) / 2 만큼의 답을 얻을 수 있다. 이렇게 되면 후보를 지정해 주고 직접 거리를 계산해 줄 필요가 없어진다.

이제, 결국 문제는 다음과 같은 질의를 빠르게 처리하는 것이다:

• $\overline{pq}$ 의 수직이등분선에 평행하고, $p, q$ 를 각각 지나는 두 직선 사이의 영역에 직선이 있는가?
• $\overline{pq}$ 에 대해서, $ccw(p, q, r) > 0$ 인 점 중 $\overline{pq}$ 에 가장 가까운 점, $ccw(p, q, r) < 0$ 인 점 중 $\overline{pq}$ 에 가장 가까운 점이 무엇인가?

특정한 방향 벡터 $v$ 를 고정하고, 모든 점을 $v$ 와의 외적 값이 증가하는 순서대로 점을 정렬하자. (정확하게 표현하기 위해 조금 비직관적으로 설명하였다. 직관적이지만 틀린 설명 방식은 다음과 같다: $(-10^{100}, 0)$ 과 점 $v - (10^{100}, 0)$ 를 잇는 직선과의 거리가 증가하는 순으로 정렬했다고 생각할 수도 있고, 모든 점에서 $v$ 방향으로 양 옆에 직선을 그었을 때의 $y$ 절편을 기준으로 정렬했다고 생각할 수도 있다.) 이 때 위 질의는 다음과 같은 식으로 해석될 수 있다:

• $\overline{pq}$ 에 수직한 방향벡터를 기준으로 정렬했을 때, $p, q$ 가 정렬된 배열 상에서 인접한 위치에 있는가?
• $\overline{pq}$ 에 평행한 방향벡터를 기준으로 정렬하면 $p, q$ 는 정렬된 배열 상 인접한 위치에 있게 된다. 이 위치를 $i, i + 1$ 이라 할 때, $i-1, i+2$ 번 위치에 있는 점은 무엇인가?

답을 구해야 하는 방향 벡터가 $O(n^2)$ 개 존재하니 이러한 방식은 문제를 해결하기 좋지 않아 보인다. 하지만, 각도를 기준으로 sweeping을 하는 식으로 위 질의를 오프라인으로 처리할 수 있다. 일반성을 잃지 않고 방향 벡터들이 $x$ 좌표가 증가하는 방향으로 향한다고 하자. 초기 $v$ 가 $(0, -1)$ 방향으로 향한다고 하면, 각 점은 $x$ 좌표가 증가하는 순으로 정렬되어 있을 것이다. 이 과정에서 $v$ 를 점점 시계 반대 방향으로 회전시키면, $v$ 의 방향벡터가 $\overline{pq}$ 와 평행해지는 순간, 두 점 $p, q$ 의 위치가 바뀌게 되고, 이러한 식으로 계속 $v$ 를 $(0, 1)$ 방향으로 돌리다 보면 결국 $x$ 좌표가 감소하는 순으로 정렬되어 있을 것이다. 이 과정의 중간에서, $v$ 의 방향벡터가 $\overline{pq}$ 와 평행해 지는 순간에는, 모든 점들이 방향벡터 $\overline{pq}$ 순으로 정렬되어 있음을 알 수 있다. 고로, 모든 중요한 이벤트 $\overline{pq}$ 를 각도 순으로 정렬한 후, 두 점의 위치를 바꾸는 것을 시뮬레이션하면서 정렬된 배열을 관리하고, 그 와중에 주어진 쿼리를 처리할 수 있다.

이제 문제는 다음과 같이 해결할 수 있다. 모든 점 $p, q$ 에 대해서, $\overline{pq}$ 에 수직하거나 평행한 방향벡터를 모두 모아 각도순으로 정렬한다. 만약 $\overline{pq}$ 에 평행한 방향벡터가 나온다면 두 점을 바꿔주는 식으로 배열을 관리해줄 경우, 각 이벤트를 처리하는 순간 해당 이벤트로 주어진 방향벡터를 기준으로 모든 점들이 정렬되어 있다. 고로 각 질의를 $O(1)$ 시간에 응답해 줄 수 있다. 이러한 방식으로 문제를 해결하면, 각도 정렬에 가장 많은 시간이 소모되므로 $O(N^2 \log N)$ 시간에 문제가 해결된다.

Subtask 5 (100점)

세 점이 한 직선 상에 주어진다고 하면, 단순히 두 직선 사이가 비어있는 지를 판별하는 것이 “배열 상에서 인접한지” 로 판별이 되지 않는다고 생각할 수 있다. 같은 기울기의 점들이 여러개가 있으면, 배열 상에서 인접하지 않아도 두 직선 사이가 비어있을 수 있기 때문이다. 하지만, 그럼에도 불구하고 인접함을 판별하는 것만으로 문제를 해결할 수 있다. 다음과 같은 두 가지 사항만 신경써 주면 된다:

• 같은 방향벡터의 이벤트가 여러 개가 있다면, 이벤트를 모두 처리한 후 해당 선과 평행한 점들이 모두 순서가 뒤집히게끔 이벤트들을 잘 나열한다.
• 각도마다 consistent한 순서를 유지하기 위해서, 같은 기울기의 이벤트가 여러 개 있으면, 스왑 이벤트를 모두 처리한 후 쿼리를 처리한다.

이렇게 될 경우, $p, q$ 가 정렬된 배열 상 인접한 위치에 있지 않더라도, 배열 상 인접한 위치에 있으며 $p, q$ 와 동일한 값을 반환하는 다른 점이 존재한다. 고로, 크게 다르지 않은 코드로 똑같이 문제를 해결할 수 있다. 이를 관찰하지 못했다면, 적당한 이진 탐색을 통해서도 문제를 해결할 수 있으며, 이에 대해서는 설명을 생략한다. 시간 복잡도는 여전히 $O(N^2 \log N)$ 이다.

여담으로, 이 문제는 Doubly-connected edge list 자료 구조를 사용하여 $O(N^2)$ 시간 복잡도에도 해결할 수 있다. 실제 대회에서 사용할 이유가 있을 만큼 고성능은 아니라고 생각하나, 관심이 있다면 배워 보는 것을 추천한다 (Looking for a Challenge p144 참고).