Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
SIGNAL - Tín hiệu |
Để chuẩn bị cho ASIAD 2010, thành phố Quảng Châu, Trung Quốc dự định lắp đặt 1 số trạm thu tín hiệu từ các địa điểm thi đấu trên khắp thành phố. Có N địa điểm thi đấu, có thể biểu thị bằng N điểm trên mặt phẳng. Trạm thu tín hiệu là 1 đường tròn đi qua 3 địa điểm thi đấu, và nó sẽ nhận thông tin từ tất cả các địa điểm thi đấu nằm trong hình tròn đó.
Xét ví dụ sau:
Trong hình, ta có 4 địa điểm thi đấu nằm tại A,B,C,D. Khi đó, trạm thu tín hiệu đi qua A,C,D (kí hiệu là (ACD)) và (ABD) chỉ chứa 3 điểm, trong khi (ABC) và (BCD) chứa cả 4 điểm. Như vậy, trung bình 1 trạm thu tín hiệu sẽ thu được (4 + 4 + 3 + 3)/4 = 3.5 địa điểm thi đấu.
Yêu cầu:
-
Cho biết tọa độ của N điểm trên mặt phẳng, xác định số địa điểm thi đấu trung bình mà 1 trạm thu tín hiệu có thể nhận được
Input:
-
Dòng đầu tiên ghi số nguyên dương N là số địa điểm thi đấu
-
N dòng sau, mỗi dòng gồm 2 số nguyên x[i],y[i] là tọa độ của điểm thi đấu thứ i
Output:
-
Gồm 1 dòng duy nhất ghi 1 số thực: kết quả bài toán. Kết quả cần được viết chính xác đến 6 chữ số sau dấu phẩy thập phân
Giới hạn:
-
3 <= N <= 1500
-
-10^6 <= x[i],y[i] <= 10^6
-
Không có 3 điểm nào thẳng hàng
-
Không có 4 điểm nào nằm trên cùng 1 đường tròn
Ví dụ:
Input 4 0 2 4 4 0 0 2 0
Input 10 -50 46 12 -45 -75 -9 63 -90 -55 58 34 -93 12 -56 -39 -92 -94 2 -97 56 |
Output 3.500000
Output 5.916667 |
Được gửi lên bởi: | Trần Hải Đăng |
Ngày: | 2010-10-26 |
Thời gian chạy: | 1s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED |
Nguồn bài: | Nguyễn Vương Linh dịch từ Asia Pacific Informatics Olympiad 2010 |
hide comments
2020-10-23 06:09:58
Last edit: 2020-10-23 15:09:54 |
|
2020-10-23 06:05:58
dijkstra 1 dam |
|
2020-10-23 06:05:12
Trau EZ AC :D _ThanhTuyenA2K48_ Last edit: 2020-10-23 06:06:41 |
|
2010-11-25 05:40:25 Tran Dang Tuan Anh
uh, cái đoạn sort cũng giống :p. Last edit: 2010-11-25 13:59:58 |
|
2010-11-10 17:09:22 Tue Le
Cảm ơn bạn Linh vì một bài tập hay! Sau một số nhận xét toán học, có thể đưa về tricount trong đề thi USACO US Open 2010 Last edit: 2011-04-28 18:44:24 |