NKSPILJA - Hang động

Giới hạn
  • Thời gian: 0.081s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

 

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 t1, t2,..., tN . 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 ti+1 .

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

Hình minh họa

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 Xi, Yi (0 ≤ Xi, Yi ≤ 100,000), là tọa độ đỉnh thứ i của nền hang động. Các giá trị Xi 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

  • Người up: paulmcvn
  • Nguồn bài: VNOI Marathon '08 - Practice RoundSource: Croatian OI 2004