APIO '10 P3 - Signaling

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

A telecom company is developing a GSM network in the city of Beijing. There are n houses in the city that need to be covered by the network. Due to budget constraints, the company can install only a single antenna.

To simplify the placement of this antenna, the location will be determined by picking 3 of the n houses to make a circle and then placing the antenna at the center of this circle. The range of the antenna will be such that all houses that lie within this circle, including those on the boundary of the circle, are covered.

The company plans to pick the 3 houses at random, so they want to compute the average number of houses that will be covered across all possible choices for the location of the antenna.

For example, suppose there are 4 houses, A, B, C and D located as shown in the figure below.

If we choose the circle defined by ABC or BCD, every house is covered. If we choose the circle defined by ACD or ABD, the fourth house is not within the circle covered by the antenna. Therefore, the average number of houses covered is \frac 1 4 (4 + 4 + 3 + 3) = 3.5.

Your task is to compute the average number of houses covered by the signal, given the locations of the houses. The positions of the houses are given in terms of a 2-dimensional coordinate system in which all houses have integer coordinates. You are guaranteed that no three houses lie on the same line and no four of them lie on the same circle.

Input Specification

The first line of input contains a single positive integer n, the total number of houses. This is followed by n lines, describing the locations of the houses. For i \in \{1, 2, \dots, n\}, the coordinates of house i are given by a pair of integers x_i and y_i on line i+1 of the input, separated by spaces.

Output Specification

The output should contain a single real number, the average number of houses that will be covered by the signal. The absolute error of the result should be less than or equal to 0.01.

Sample Input

4
0 2
4 4
0 0
2 0

Sample Output

3.500

Explanation for Sample Output

3.5, 3.50, 3.500, \dots are all considered correct outputs, moreover, 3.51, 3.49, 3.499999, \dots are also acceptable.

Constraints

  • In 100\% of the test cases, for i \in \{1, 2, \dots, n\}, the coordinates (x_i, y_i) of house i are both integers such that -1\,000\,000 \le x_i, y_i \le 1\,000\,000. No three houses are located on a line and no four houses are located on a circle.
  • In 40\% of the test cases, n \le 100.
  • In 70\% of the test cases, n \le 500.
  • In 100\% of the test cases, 3 \le n \le 1\,500.

Comments


  • 2
    daoboyang41  commented on Oct. 6, 2018, 7:36 p.m. edit 2

    Just passed it in java by submitting 4 times. It would be really nice if java's time limit is set to 1.1 s