| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P146SUMH - ROUND 6H - Đua thuyền |
Người dân nước GeoLand say mê các môn thể thao mạo hiểm đòi hỏi tư duy hình học chuyên nghiệp. Một trong những môn thể thao đó là bơi thuyền vượt bãi đá trên sông. Bản đồ con sông được vẽ trên mặt phẳng tọa độ với hệ tọa độ descartes vuông góc, hai bờ sông là hai đường thẳng song song y=0 và y=h. Bãi đá trên sông gồm n tảng đá đánh số từ 1 tới n, tảng đá thứ i có tọa độ (x_i,y_i ) trên bản đồ.
Mỗi vận động viên tham gia bài thi với một thuyền thúng hình tròn. Anh ta được đặt thuyền của mình ở vị trí tùy chọn nằm hoàn toàn bên trái bãi đá và cần bơi thuyền tới một vị trí tùy chọn nằm hoàn toàn bên phải bãi đá. Thuyền được di chuyển theo hướng tùy ý nhưng không được chạm vào bờ sông hay chạm vào một tảng đá nào của bãi đá (kể cả đường biên của thuyền).
Bạn hãy tìm số nguyên d lớn nhất để mọi thuyền có đường kính <d đều có thể thực hiện được bài thi.
Input
Dòng 1 chứa hai số nguyên dương n,h (n ≤ 4000; 2 ≤ h ≤ 10^9).
n dòng tiếp theo, mỗi dòng chứa hai số nguyên dương x_i ≤ 10^9, y_i < h.
Output
Ghi ra một số nguyên duy nhất là số d tìm được.
Example
Input: 4 8
1 2
4 6
9 2
9 7 Output: 5
| Được gửi lên bởi: | adm |
| Ngày: | 2014-07-31 |
| Thời gian chạy: | 2s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
