32230번 - 현대모비스 첨단 운전자 보조 시스템 서브태스크스페셜 저지

현대모비스에서는 미래자동차 기술로 첨단 운전자 보조 시스템(ADAS) 기능을 연구개발 하고 있으며, ADAS에는 전방 충돌방지 보조(FCA), 스마트 크루즈 컨트롤(SCC), 차로 이탈방지 보조(LKA), 후측방 충돌방지 보조(BCA) 등 다양한 주행 안전/편의 기능이 포함되어 있다. 각각에 대해 간략히 소개하면 아래와 같다.

• FCA (Forward Collision-Avoidance Assist, 전방 충돌방지 보조) : 전방의 차량, 보행자 및 자전거 탑승자와 충돌하지 않도록 도와주는 주행 안전 기능으로, 전방을 인식하고, 선행 차량이 갑자기 속도를 줄이거나 충돌 위험을 감지하면 경고한다. 경고 후에도 충돌 위험이 높아지면 자동으로 제동을 도와준다.
• SCC (Smart Cruise Control, 스마트 크루즈 컨트롤) : 앞차와의 거리를 유지하며 운전자가 설정한 속도로 주행하도록 도와주는 주행 편의 기능으로, 차간거리를 단계 별로 선택할 수 있으며, 전방 차량을 인식하여 자동으로 차간거리 및 설정 속도를 유지하면서 주행한다.
• LKA (Lane Keeping Assist, 차로 이탈방지 보조) : 차로를 이탈하지 않고 주행하도록 도와주는 주행 안전 기능으로, 차선을 인식하고, 방향지시등 스위치의 움직임 없이 차로 이탈을 감지하면 경고하며, 차로를 이탈하지 않도록 자동으로 조향을 도와준다.
• BCA (Blind-Spot Collision-Avoidance Assist, 후측방 충돌방지 보조) : 차로변경 시 또는 평행 출차 시 후측방 차량과 충돌하지 않도록 도와주는 주행 안전 기능으로, 차선과 후측방 차량을 인식하고, 차로변경 시 후측방 차량과의 충돌 위험을 감지하면 경고한다. 경고 후에도 충돌 위험이 높아지면 자동으로 제동을 도와준다. 평행 주차상태에서 전진 출차 시 후측방 차량과의 충돌 위험을 감지하면 자동으로 제동을 도와준다.

현대모비스에서 첨단 운전자 보조 시스템을 연구하는 예영이는 차량 주행 데이터 분석을 위해 데이터 수합 영역, 위험 영역, 안전 영역으로 영역을 구분하여 각 영역을 다음과 같이 정의했다.

1. 데이터 수합 영역은 $N \geq 3$인 경우 $N$대의 주변 차량으로 이루어진 볼록 다각형 모양이다. 주변 차량은 모두 볼록 다각형의 꼭짓점을 이룬다. 단, $N=2$인 경우 데이터 수합 영역은 두 주변 차량을 잇는 선분의 모양을 가지며, $N=1$인 경우 데이터 수합 영역은 점 하나의 모양을 가진다.
2. 데이터 수합 영역이 볼록 다각형 모양인 경우, 운전자 차량은 데이터 수합 영역 내부를 자유롭게 돌아다닐 수 있다. 데이터 수합 영역의 내부는 경계를 포함하지 않는다. 운전자 차량에서 $N$대의 주변 차량으로 선분을 각각 그어, 데이터 수합 영역은 $N$개의 삼각형 영역으로 분할된다.
   1. 분할된 삼각형마다 위험 영역을 삼각형 각 변의 중점을 내접점으로 하여 삼각형에 내접하는 타원으로 정의한다. 정의되는 타원이 여러 개라면 그 중 하나를 고르며, 타원이 하나 이상 정의됨은 증명할 수 있다.
   2. 위험 영역들로 모두 둘러싸인, 운전자 차량을 포함하는 영역은 안전 영역으로 정의한다.
3. 데이터 수합 영역이 볼록 다각형 모양이 아닌 경우에는 위험 영역과 안전 영역은 정의되지 않는다.

현대모비스에서는 최악의 상황을 고려하여, 안전 영역의 넓이의 최솟값을 구하고자 한다. $N$대의 주변 차량의 정보가 주어질 때, 안전 영역의 넓이의 최솟값을 구해보자.

첫 번째 줄에 주변 차량의 대수 $N(1\leq N\leq 1\,000)$이 주어진다.

두 번째 줄부터 $N$ 줄에 걸쳐 $i$번째 차량 $P_i$의 좌표 $x_i, y_i(-10^9\leq x_i, y_i\leq 10^9)$가 공백으로 구분되어 주어진다.

$P_i$는 모두 다른 정수 좌표의 점이며, 반시계 방향 순서로 주어진다. 또한, 서로 다른 세 점이 한 직선 위에 놓이지 않는다.

첫 번째 줄에 안전 영역의 최소 넓이를 출력한다. 안전 영역이 정의되지 않는다면 넓이가 $0$이라고 생각한다.

정답과의 절대오차 또는 상대오차가 $10^{-9}$ 이하이면 정답으로 인정된다.