만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

슬롯에 동전 넣기

면접 대비

시간 제한1초메모리 제한1024 MB

요약
볼록 다각형을 회전해서 통과시킬 수 있는 가장 좁은 슬롯의 폭을 구합니다.
난이도

보통10점 중 4점

유형
기하, 완전 탐색
정답자
아직 제출이 없습니다

문제

작은 나라 에라티카는 세계의 다른 '지루한' 나라들이 정한 관습을 일부러 깨뜨리는 것을 자랑으로 삼는다. 가장 눈에 띄는 차이는 동전 디자인에 있다. 사람이 주머니나 지갑 속 동전의 가치를 손의 감촉만으로 알아볼 수 있어야 한다고 보고, 에라티카는 동전을 다각형으로 설계한다. 안정성을 위해 동전은 볼록하며, 가장자리에 홈이 파여 있지 않다. 다만 전체 모양은 꽤 불규칙할 수 있다.

에라티카 자판기 회사는 이 나라에서 자판기를 만드는 유일한 제조사로, 새로 발행될 동전의 설계도를 받았다. 자판기는 동전이 슬롯을 통해 직육면체 모양의 채널로 들어가도록 설계되어 있다. 슬롯은 그 직육면체의 열린 면이다. 동전이 얇아서 채널은 좁지만, 동전 전체를 담을 만큼은 길다. 기계 바깥에서 보면 슬롯은 직사각형 구멍으로 보인다.

회사는 새 동전을 몇 번 회전시킨 뒤 슬롯에 밀어 넣을 수 있도록, 필요한 슬롯의 최소 크기를 알고 싶어 한다.

입력

입력은 다각형 동전의 변의 개수 NN이 적힌 줄로 시작한다. 3≤N≤203 \leq N \leq 20이다.

이어서 NN개의 줄이 주어지며, 각 줄에는 다각형 꼭짓점의 좌표를 나타내는 실수 xx와 yy가 있다. 0.0≤x,y≤100.00.0 \leq x, y \leq 100.0이다.

NN개의 꼭짓점은 모두 서로 다르며, 동전 테두리를 따라 시계 방향 순서로 주어진다.

출력

동전이 통과할 수 있는 최소 슬롯 크기를 나타내는 실수를 소수점 아래 둘째 자리까지 한 줄에 출력한다. 정답과의 차이가 ±0.01\pm 0.01 이내이면 정답으로 인정한다.

예제2

  1. 예제 1

    입력
    3
    0 0
    0.71 3.54
    4.21 4.21
    
    예상 출력
    2.00
    
  2. 예제 2

    입력
    6
    10 12.5
    10 17.5
    15 20
    20 17.5
    20 12.5
    15 10
    
    예상 출력
    8.94