X Clash

이동 방향의 조건

우선 다각형의 꼭짓점 순서가 반시계 방향이라고 생각하자. $\ell$ 위에 완전히 놓인 변을 제외한 각 변의 방향 벡터를 $e$라 하자. 충돌 없이 아주 조금 움직일 수 있는 벡터 $v$는 반드시

$$e \times v \geq 0$$

을 만족한다. 이 값이 음수이면 그 변의 내부에 있는 점 근처에서 양의 넓이만큼 벽을 침범한다. 등호일 때는 경계를 따라 미끄러지므로 허용한다. $\ell$ 위의 변은 벽의 바깥과 맞닿아 있으므로 이 조건을 적용하지 않는다.

이 조건을 모든 해당 변에 대해 만족하면서 $H$의 바깥을 향하는 $v$가 있으면, 그 방향으로 계속 움직여 꺼낼 수 있다. $v$와 평행한 직선으로 다각형을 잘라 보자. 벽 내부에 있는 경계에서는 $v$ 방향으로 내부에서 외부로 나갈 수 없으므로, 각 단면의 내부는 벽의 입구까지 이어지는 하나의 구간이다. 따라서 이 구간을 입구 쪽으로 옮겨도 벽을 침범하지 않는다. 꼭짓점을 지나는 단면은 극한으로 처리할 수 있다.

반대로 어떤 연속 경로로 꺼낼 수 있다면, 처음 위치와 다른 충분히 가까운 위치로의 변위는 위 부등식을 모두 만족한다. $\ell$ 위의 변들은 모두 같은 방향을 향한다. 전체 변 벡터의 합이 $0$이라는 사실로부터, 가능한 0이 아닌 변위는 반드시 $H$ 바깥을 향한다. 경계선과 평행한 변위라면 모든 변과 평행해야 해서 다각형의 넓이가 양수라는 조건에 모순이다. 따라서 방향을 도중에 바꾸어야만 가능한 경우는 없다.

원안의 풀이: $O(N^2)$

가능한 방향들이 이루는 닫힌 각도 구간의 경계는 어떤 변과 평행하다. 따라서 각 변의 두 방향을 후보로 두고 모든 부등식과 바깥 방향 조건을 검사하면 된다. 넓이가 양수인 다각형에서는 가능한 방향이 경계선에 평행한 비영벡터일 수 없으므로, 가능한 방향이 있다면 이러한 후보도 존재한다. 첨부한 naive 풀이가 이 방법이며 전체 제한을 통과한다.

선형 시간 풀이

$b=P_2-P_1$이고, $s$를 꼭짓점 순서가 반시계 방향이면 $1$, 시계 방향이면 이라 하자. 로 정의한다. 바깥 방향 벡터는 양의 배율을 무시하면

$$v=t b-sR(b)$$

로 나타낼 수 있다. 각 변에 대한 조건은

$$s(e\times b)t\geq e\cdot b$$

이다. 왼쪽 계수가 양수이면 $t$의 하한, 음수이면 상한을 갱신한다. 계수가 $0$이고 오른쪽 값이 양수이면 불가능하다. 최종 하한이 상한보다 크면 불가능하고, 같아도 가능하다.

분수는 분자와 양의 분모로 보관하고 교차 곱으로 비교한다. 시간 복잡도는 $O(N)$, 입력 저장 공간은 $O(N)$이다. 좌표 차의 절댓값은 $20\,000$ 이하이고 내적과 외적의 절댓값은 $8\cdot10^8$ 이하이다. 분수 비교의 각 곱은 이하이므로 signed 64-bit 정수로 충분하다.

서브태스크 1은 삼각형이다. 입구의 반대쪽 꼭짓점에서 입구의 내부점을 향해 이동하면 되므로 항상 가능하다. 입력을 읽는 비용을 포함하면 $O(N)$이다.

Solution written by GPT