Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKSPILJA - Hang động

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 ti 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 ≤ 100000), 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

Được gửi lên bởi:Jimmy
Ngày:2007-12-07
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Nguồn bài:VNOI Marathon '08 - Practice Round
Source: Croatian OI 2004

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.