시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 69 21 15 26.786%

문제

주호의 조상은 그의 마을에 수천 년 전에 동굴에서 살았다.
  주호는 그녀가 조상의 흔적들을 찾을 수 있는 유일한 사람이라 결정짓고 그녀는 탐험하기를 결심했다. 그러므로 그녀는 새로운 바지와 부츠와 삽을 구입했다. 하지만 그녀는 현재의 삽으로는 발굴하기 힘들다는 것을 깨닫고 그녀의 모든 돈을 삽을 업그레이드하는데 쏟아 부었다. 결국 그녀는 램프 하나 살 돈만 남기에 이르렀다.
  주호는 그녀가 전체 지면을 내다볼 수 있는 지점을 찾기를 원했으므로, 동굴 속 모든 지면을 밝게 하기위해 그녀가 램프를 놓아야할 가장 높이가 낮은 곳을 결정하는데 도움을 줘야한다.
  동굴은 N개의 꼭지점이 있고 이들은 서로 연속적으로 연결되어 있다.
  그 지면은 항상 왼쪽에서 오른쪽으로 입력이 되어진다. 즉 ti의 x좌표는 ti+1의 x좌표보다 작다.

램프는 반드시 모든 지면을 비추는 동굴의 지면 위에 놓여야 한다. 이것을 더 정확히 놓기 위해, 램프가 놓이는 x좌표는 첫 번째 x좌표와 마지막 x좌표 사이여야 한다. 그리고 램프의 y좌표는 그 지면에 해당하는 y좌표여야 한다.
  우리는 선분으로 형성된 동굴의 지면까지 도달하는데 다른 선분을 관통하지 않으면 비출 수 있다고 말할 수 있다.
  전체 지면을 비출 수 있는 지점 중에 가장 낮은 높이를 구하시오.
  우리는 결과가 1,000,000보다 같거나 항상 작다고 가정한다.

입력

첫 번째 줄에 동굴의 꼭지점 개수 N, 2 ≤ N ≤ 5000이 들어온다. 그리고 다음 N 줄에 이 꼭지점의 좌표 Xi와 Yi가 차례로 들어온다. 다시 한번 말하지만 Xi는 오름차순으로 입력된다.

출력

첫 번째 줄에 램프를 놓은 높이를 소수점 둘째자리까지 출력한다. 오차를 0.01까지 허용한다.

예제 입력

6 
0 0 
10 0 
11 1 
15 1 
16 0 
25 0 

예제 출력

3.00

힌트