P3630 [APIO2010] Signal Coverage

A telecom company is building a GSM network in Beijing. There are $n$ houses in the city that need signal coverage. Due to budget constraints, the company can install only one antenna. Each house is represented by a point in the plane. To simplify placement, the company will choose 3 houses and take their circumcircle, then place the antenna at the center of that circle. Every house that lies on or inside this circle will be covered by the antenna. The company will choose 3 houses uniformly at random from all houses in the city. They want to know, over all possible antenna placements, the average number of houses that will be covered. For example, suppose there are 4 houses $A, B, C, D$, positioned as in the figure:  If we choose the circumcircle of $A, B, C$ or $B, C, D$, then all houses are covered. If we choose $A, C, D$ or $A, B, D$, the remaining house will not be covered. Therefore, the average is $(4 + 4 + 3 + 3) / 4 = 3.50$. Given the positions of all houses, your task is to compute the average number of houses covered. Assume every house has integer 2D coordinates, no three houses are collinear, and no four houses are cocircular.

The first line contains a positive integer $n$, the total number of houses. The next $n$ lines describe the positions of the houses. For $i = 1, 2, \ldots, n$, the $i$-th house has coordinates given by a pair of integers $x_i$ and $y_i$, separated by a space.

Output a real number: the average number of houses covered by the antenna. The absolute error from the exact value must not exceed $0.01$.

Sample note: Any of 3.5, 3.50, 3.500, … is correct. In addition, 3.49, 3.51, 3.499999, … are also acceptable. Constraints: - For all $i = 1, 2, \ldots, n$, the coordinates $(x_i, y_i)$ are integers and $-1{,}000{,}000 \le x_i, y_i \le 1{,}000{,}000$. No three houses are collinear, and no four houses are cocircular. - 40% of the testdata: $n \le 100$. - 70% of the testdata: $n \le 500$. - 100% of the testdata: $3 \le n \le 1{,}500$. Translated by ChatGPT 5