Giải bài trực tuyến

Để 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ụ: