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.|

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:0.891s
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
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.