| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P145PROJ - ROUND 5J - Phủ sóng |
Khu xóm nhà Tí rủ nhau cùng lắp đặt wifi. Tuy nhiên, để tiết kiệm, các gia đình chỉ quyết định lắp đặt một trạm phát wifi tại “trung tâm” của xóm. Sau khi gọi nhà cung cấp dịch vụ đến, một vấn đề đã phát sinh: các gia đình tranh cãi với nhau xem đâu là trung tâm là xóm?
Anh kĩ sư thấy buồn vì đến chả được công việc gì. Trong khi họ còn đang tranh cãi thì anh đang tính thử xem trung bình sẽ có bao nhiêu hộ gia đình sử dụng được wifi? Anh chọn ngẫu nhiên 3 ngôi nhà và lấy điểm cách đều cả 3 ngôi nhà làm “trung tâm”, đặt thiết bị phát wifi ở đó. Thiết bị phát wifi sẽ phủ sóng kín vừa đủ vùng không gian hình tròn chứa 3 ngôi nhà được chọn.
Các bạn hãy giúp anh kĩ sư giải quyết bài toán này!
Input
Dòng đầu tiên chứa số nguyên dương n (n <= 1500) là số ngôi nhà.
n dòng tiếp theo, mỗi dòng gồm 2 số nguyên x_i, y_i (−1000000 ≤ x_i, y)i ≤ 1000000) là tọa độ của ngôi nhà thứ i.
Input đảm bảo không có 3 điểm nào thẳng hàng và không có 4 điểm nào cùng nằm trên một đường tròn.
Output
In ra số ngôi nhà trung bình được phủ sóng, sai số không quá 10^-2.
Example
Input: 4
0 2
4 4
0 0
2 0 Output: 3.500
Giải thích test:
Nếu chọn 3 hộ ABC hay BCD thì sẽ phủ sóng được tất cả các hộ. Nếu chọn 3 hộ ACD hay ABD
thì chỉ phủ sóng được 3 hộ. Như vậy, trung bình có 3.5 hộ gia đình được phủ sóng wifi.
| Được gửi lên bởi: | adm |
| Ngày: | 2014-03-05 |
| 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 |
