슬롯에 동전 넣기
면접 대비시간 제한1초메모리 제한1024 MB
볼록 다각형을 회전해서 통과시킬 수 있는 가장 좁은 슬롯의 폭을 구합니다.
문제
작은 나라 에라티카는 세계의 다른 '지루한' 나라들이 정한 관습을 일부러 깨뜨리는 것을 자랑으로 삼는다. 가장 눈에 띄는 차이는 동전 디자인에 있다. 사람이 주머니나 지갑 속 동전의 가치를 손의 감촉만으로 알아볼 수 있어야 한다고 보고, 에라티카는 동전을 다각형으로 설계한다. 안정성을 위해 동전은 볼록하며, 가장자리에 홈이 파여 있지 않다. 다만 전체 모양은 꽤 불규칙할 수 있다.
에라티카 자판기 회사는 이 나라에서 자판기를 만드는 유일한 제조사로, 새로 발행될 동전의 설계도를 받았다. 자판기는 동전이 슬롯을 통해 직육면체 모양의 채널로 들어가도록 설계되어 있다. 슬롯은 그 직육면체의 열린 면이다. 동전이 얇아서 채널은 좁지만, 동전 전체를 담을 만큼은 길다. 기계 바깥에서 보면 슬롯은 직사각형 구멍으로 보인다.
회사는 새 동전을 몇 번 회전시킨 뒤 슬롯에 밀어 넣을 수 있도록, 필요한 슬롯의 최소 크기를 알고 싶어 한다.
입력
입력은 다각형 동전의 변의 개수 이 적힌 줄로 시작한다. 이다.
이어서 개의 줄이 주어지며, 각 줄에는 다각형 꼭짓점의 좌표를 나타내는 실수 와 가 있다. 이다.
개의 꼭짓점은 모두 서로 다르며, 동전 테두리를 따라 시계 방향 순서로 주어진다.
출력
동전이 통과할 수 있는 최소 슬롯 크기를 나타내는 실수를 소수점 아래 둘째 자리까지 한 줄에 출력한다. 정답과의 차이가 이내이면 정답으로 인정한다.