Một công ty viễn thông đang xây dựng mạng GSM tại Bắc Kinh. Trong thành phố có \(n\) ngôi nhà cần được phủ sóng. Do ngân sách hạn chế, công ty chỉ có thể lắp đặt một ăng-ten.

Để đơn giản hóa việc chọn vị trí, công ty sẽ chọn ba trong số \(n\) ngôi nhà, dựng đường tròn đi qua chúng và đặt ăng-ten tại tâm đường tròn đó. Phạm vi phủ sóng bao gồm tất cả các ngôi nhà nằm bên trong hoặc trên đường tròn.

Công ty dự định chọn ngẫu nhiên ba ngôi nhà, với mọi bộ ba có khả năng được chọn như nhau. Hãy tính số ngôi nhà được phủ sóng trung bình trên tất cả các cách chọn.

Vị trí các ngôi nhà được cho bằng tọa độ nguyên trong hệ tọa độ hai chiều. Không có ba ngôi nhà nào thẳng hàng và không có bốn ngôi nhà nào cùng nằm trên một đường tròn.

Dữ liệu vào

Dòng đầu chứa số nguyên dương \(n\), số ngôi nhà. Tiếp theo là \(n\) dòng mô tả vị trí các ngôi nhà. Với mỗi \(i\) từ \(1\) đến \(n\), dòng thứ \(i+1\) chứa hai số nguyên \(x_i,y_i\) cách nhau bởi dấu cách, là tọa độ ngôi nhà thứ \(i\).

Dữ liệu ra

In một số thực: số ngôi nhà được phủ sóng trung bình. Sai số tuyệt đối của kết quả không được vượt quá \(0.01\).

Ràng buộc

• \(3\le n\le 1\,500\).
• \(x_i,y_i\) là các số nguyên và \(-1\,000\,000\le x_i,y_i\le 1\,000\,000\) với mọi \(1\le i\le n\).
• Không có ba ngôi nhà nào thẳng hàng.
• Không có bốn ngôi nhà nào cùng nằm trên một đường tròn.

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Ví dụ

4
0 2
4 4
0 0
2 0

3.500

    Các kết quả $3.5$, $3.50$, $3.500$, … đều đúng. Các kết quả $3.51$, $3.49$, $3.499999$, … cũng được chấp nhận.

Nguồn

APIO 2010 — Signaling, đề tiếng Anh phiên bản 1.2.