DMOPC '21 Contest 4 P6 - Balanced Line

View as PDF

Submit solution


Points: 35 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

In return for Petep's present, Reter decides to bake some Christmas cookies for Petep! A cookie can be modelled as a flat Cartesian plane, and Reter has already placed N chocolate chips at points (x_i,y_i).

To add the finishing touches to the cookie, Reter wants to add a straight, non-vertical line of icing that passes through at least two of the N chocolate chips. He would like the chips on the two sides of the line to look as balanced as possible. Thus, he defines the balance value of a non-vertical line \ell to be the absolute difference between the sum of the vertical distances to \ell of all points above \ell, and the sum of the vertical distances to \ell of all points below \ell. The vertical distance of a point (x,y) to a non-vertical line \ell is the distance one needs to translate (x,y) vertically so that it lies on \ell. Reter wonders what the smallest balance value that a non-vertical line passing through at least two of the points is.

However, before adding the line of icing, Reter realizes that Petep might see the cookie from a different direction! Thus, he now has Q queries. Each query consists of a point (a_i,b_i), and Reter would like to know: If all the points are rotated about the origin so that (a_i,b_i) now lies on the positive x-axis, what is the smallest possible balance value?

Constraints

3 \le N \le 3 \times 10^5

1 \le Q \le 3 \times 10^5

-10^6 \le x_i, y_i, a_i, b_i \le 10^6

All N points (x_i,y_i) are distinct.

There does not exist a line that contains all N points (x_i,y_i).

For all 1 \le i \le Q, (a_i,b_i) \ne (0,0).

Subtask 1 [10%]

3 \le N \le 2 \times 10^3

1 \le Q \le 5

Subtask 2 [20%]

3 \le N \le 2 \times 10^3

1 \le Q \le 2 \times 10^3

Subtask 3 [25%]

3 \le N \le 2 \times 10^3

Subtask 4 [25%]

1 \le Q \le 5

Subtask 5 [20%]

No additional constraints.

Input Specification

The first line contains two space-separated integers: N and Q.

The next N lines each contain two space-separated integers: x_i and y_i.

The next Q lines each contain two space-separated integers: a_i and b_i.

Output Specification

Output Q lines, the answer to each query. Your output will be considered correct if the absolute or relative error of each value does not exceed 10^{-4}.

Sample Input 1

4 2
-2 -2
-1 3
2 -1
3 -2
1 0
1 -3

Sample Output 1

3.500000000
3.162277660

Explanation for Sample 1

For the first query, it is optimal to choose the line that passes through the 1st and 3rd points:

For the second query, it is optimal to choose the line that passes through the 3rd and 4th points:

Sample Input 2

4 2
-2 2
0 1
1 3
2 0
1 0
2 -1

Sample Output 2

0.000000000
2.236067977

Explanation for Sample 2

For the first query, it is optimal to choose the line that passes through the 2nd and 3rd points.

For the second query, it is optimal to choose the line that passes through the 1st, 2nd and 4th points.


Comments

There are no comments at the moment.