[Python] 32230번 현대모비스 첨단 운전자 보조 시스템

 

https://www.acmicpc.net/problem/32230

---

 

24/09/10

 

 

내가 출제한 문제고, 에디토리얼이 나오려면 좀 걸릴 것 같아서 미리 내 문제만 먼저 해설을 작성해보고자 한다. 

---

 

문제 접근 방식:

 

 

문제의 요구 사항은 안전 영역의 최솟값을 구하는 것이다.

 

서브태스크별로 할 수 있는 풀이를 적고자 한다.

 

• 서브태스크 1

문제를 잘 읽고 $N \geq 3$일때 볼록 다각형이 만들어지고, 그렇지 않은 경우 볼록 다각형이 만들어지지 않음을 파악한다.

 

따라서, $0$을 출력하면 받을 수 있다.

 

• 서브태스크 2 

문제의 핵심 부분이다.

 

문제에서 유의 깊게 관찰할 수 있는 부분들은 $10^{-9}$과 같은 빡빡한 오차, $1$초와 같은 수상한 제한, 수상하게 큰 좌표 제한 등이 존재한다.

 

가장 나이브하게 생각할 수 있는 것은, 직접 적분을 하는 것이다.

 

하지만 이는 구현하기 힘들 뿐더러 식 정리도 만만치 않아보이고, 무엇보다 빡빡한 오차와 큰 좌표 제한에 의해 걸러질 것이라는 확신을 가지면 충분하다.

 

풀이의 핵심은 자동차가 내부에서 어떻게 움직이던 간에 안전 영역의 넓이는 일정하다는 사실이다.

 

이에 대한 증명은 다음과 같다.

 

1. 자동차가 위치한 점을 임의로 $O$라고 하고, 주변 차량이 위치한 점은 $P_i$라고 하자.

 

2. 분할된 삼각형 영역을 생각해보자. 즉, $\triangle OP_i P_{i+1}$을 생각해보자. 편의상 이를 $T_i$라고 하겠다.

 

3. 그리고 $P_i P_{i+1}$을 밑변으로 하는 정삼각형을 생각해보자. 편의상 이를 $S_i$라고 하겠다.

4. $T_i$는 $S_i$를 아핀변환시킨 형태이다. 즉, $S_i$에서 $\overline{P_iP_{i+1}}$을 고정하고 $S_i$의 꼭짓점을 움직인 모습이라고 생각할 수 있다.

 

여기서 아핀 변환이란?

아핀 변환의 엄밀한 "정의"는 위키백과를 참고하자. 여기서는 이 문제에 필요한 핵심적인 아핀 변환의 성질만을 간단히 설명하겠다.
아핀 변환은 선형성과 평행성을 보존하는 변환이다. 2차원 평면에의 평행이동, 대칭이동, 회전이동, 확장(가로나 세로 등), 전단(Shearing)이동과 이들을 합성한 변환들은 모두 아핀변환에 속한다.
아핀변환의 가장 큰 특징은, 변환 이전과 변환 이후의 각 넓이의 비가 일정한 상수배가 된다는 점이다. 즉, 변환 이전의 두 넓이의 비율은 변환 이후의 두 넓이의 비율과 동일하다. 즉, 넓이의 비율을 보존하는 변환이다. 주의할 점은, 아핀변환은 길이나 각도의 비율을 보존하지 않는다는 점이다.

 

$S_i$를 전단(Shearing)및 확장(Scaling)시킨 모습이 $T_i$이므로, 정확히 아핀변환에 해당됨을 확인할 수 있다.

 

5. 따라서 $T_i$의 각 변의 중점에 내접하는 내접타원이 유일함은 아핀변환에 의해 당연하다. $S_i$의 내접원이 아핀변환에 의해 변환된 모습이 $T_i$의 내접타원이기 때문이다. $S_i$의 내접원은 당연히 유일하다.

 

6. 또한, 쪼개진 안전영역의 모양은 $S_i$에서 내접원을 뺀 모양 중 $1/3$부분을 아핀변환 시킨 모습임을 확인할 수 있다. 편의상 $S_i$에서 내접원을 뺀 모양 중 $1/3$을 $R_i$라고 하자.

 

7. 쪼개진 안전영역을 편의상 $Q_i$라고 하면, $T_i : Q_i = S_i : R_i$가 성립한다. 이 비율을 구하면 $\frac{1}{3} - \frac{\pi}{9\sqrt{3}}$이다. 편의상 이 숫자를 $C$라고 하자.

 

8. 따라서, 다각형의 넓이는 $\sum T_i$이고, 안전영역의 넓이는 여기에 위의 비율을 곱한 $\sum Q_i = C \sum T_i$가 된다.

 

슈타이너 내접타원에 대한 이야기가 나오기도 했는데, 이와는 무관한 문제이다. 여담으로 이 문제를 초기에 세팅했을 당시의 의도는 마든정리를 사용하는 문제였으나, 굳이 그렇게 만들 필요를 못느끼기도 했고 위와 같은 좋은 풀이 방안을 발견하여 방향을 틀었다.

 

---

코드는 생략.