BOJ 32118 감옥

먼저, 다각형 내부 판정을 할 수 있으면 다음 죄수의 위치를 이동시키는 것은 간단합니다. C++/Rust의 경우, 다음과 같이 구현할 수 있습니다.

• $(x_i, y_i)$가 다각형 내부에 있는 경우: $(x_{i+1}', y_{i+1}') = (2x_{i+1} - x_i, 2y{i+1} - y_i)$
• $(x_i, y_i)$가 다각형 외부에 있는 경우: $(x_{i+1}', y_{i+1}') = ((x_i + x_{i+1})/2, (y_i + y_{i+1})/2)$ (여기서 $/$는 부호 있는 정수 나눗셈입니다. 이를 이용하면 문제에서 요구하는 방향으로 반올림(?)이 이루어집니다.)

이제 문제는 점이 하나 주어질 때 다각형 내부에 있는지 여부를 판정하는 것입니다.

문제 조건 상, 다각형의 영역은 다각형의 모든 꼭짓점으로부터 원점으로 선을 그어서 얻는 삼각형들의 합집합과 일치하며, 이러한 삼각형들은 서로 겹치지 않습니다. 대신, 다각형에서 이웃한 두 꼭짓점이 원점과 일렬로 위치할 수 있습니다.

어떤 점 $(x, y)$가 주어지면, 다음과 같은 경우가 가능합니다.

• 원점에서 어떤 꼭짓점을 향해서 반직선을 그었을 때 그 위에 있는 경우
• 그렇지 않은 경우: 원점에서 어떤 이웃한 두 꼭짓점을 향해서 반직선을 그었을 때 그 영역 안에 있는 경우

주어진 점이 어느 반직선 또는 어느 영역에 속하는지를 확인하기 위해서는 이분 탐색을 하고 싶은데, CCW를 가지고 방향을 판정한 결과는 false*, true*, false*이거나 true*, false*, true*의 형태로 나타날 수 있습니다. 이를 회피하기 위해서, 주어진 점이 1-2사분면에 있는지, 3-4사분면에 있는지에 따라서 절반의 배열에 대해 이분 탐색을 할 수 있습니다.

이렇게 하여 점을 포함하는 반직선이나 영역을 찾았다면, 다음과 같이 판정할 수 있습니다.

• 반직선 위에 있는 경우: 반직선 위의 모든 꼭짓점 중 가장 먼 것과 원점으로부터의 거리를 비교
• 영역 위에 있는 경우: 변의 벡터를 기준으로 왼쪽에 있는지 판정