VNOI Marathon 08

Gần ngôi làng có một hang động tổ tiên của Mirko đã sống hàng nghìn năm về trước. Muốn là người đầu tiên phát hiện ra những di vật cổ đại này, Mirko chuẩn bị cho chuyến đi khám phá hang động. Do hang động không có điện nên Mirko phải mua một ngọn đèn. Mirko muốn chọn một vị trí để từ đó có thể nhìn thấy toàn bộ nền hang động.

Tưởng tượng rằng nền hang động là một đường gấp khúc trong hệ tọa độ gồm N đỉnh t₁, t₂,..., t_N. Nền hang động luôn chạy từ trái sang phải, nghĩa là với mọi i=1,2,...,N-1 tọa độ x của t_i luôn bé hơn tọa độ x của t_i+1.

Ví dụ: (một lời giải cho ví dụ 3)

Ngọn đèn phải đặt ở một điểm nào đó "phía trên" nền hang động sao cho chiếu sáng được toàn bộ nền hang động. Chính xác hơn, tọa độ x của ngọn đèn phải được đặt giữa tọa độ x của điểm đầu và điểm cuối của hang động, và tọa độ y của ngọn đèn phải lớn hơn hoặc bằng tọa độ y của điểm nằm trên nền hang động ở cùng tọa độ x.

Ngọn đèn chiếu sáng toàn bộ hang động nếu với mọi điểm thuộc nền hang động, đoạn thẳng nối điểm đó và ngọn đèn không cắt đường gấp khúc thể hiện nền hang động. Tuy nhiên, đoạn thẳng và đường gấp khúc có thể giao nhau tại các đỉnh hoặc dọc theo một đoạn thẳng thuộc đường gấp khúc.

Yêu cầu: hãy giúp Mirko xác định độ cao nhỏ nhất có thể đặt ngọn đèn để chiếu sáng toàn bộ nền hang động. Biết rằng kết quả không vượt quá 1000000.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên N (2 ≤ N ≤ 5000) là số đỉnh của nền hang động.
• Dòng thứ i trong N dòng tiếp theo chứa 2 số nguyên X_i, Y_i (0 ≤ X_i, Y_i ≤ 100000), là tọa độ đỉnh thứ i của nền hang động. Các giá trị X_i có thứ tự tăng dần.

Kết qủa

In ra 1 số nguyên duy nhất là tọa độ y bé nhất có thể đặt được ngọn đèn, với độ chính xác 2 chữ số thập phân.

Ví dụ

Dữ liệu mẫu
6 
0 0 
10 0 
11 1 
15 1 
16 0 
25 0

Kết qủa
3.00

Dữ liệu mẫu
6
1 1
4 2
5 0
9 2
12 3
16 4

Kết qủa
2.00

Dữ liệu mẫu
6
0 10
3 7
5 0
6 1
7 4
10 5

Kết qủa
3.75