## DMOPC '21 Contest 4 P6 - Balanced Line

View as PDF

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 chocolate chips at points .

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 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 to be the absolute difference between the sum of the vertical distances to of all points above , and the sum of the vertical distances to of all points below . The vertical distance of a point to a non-vertical line is the distance one needs to translate vertically so that it lies on . 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 queries. Each query consists of a point , and Reter would like to know: If all the points are rotated about the origin so that now lies on the positive x-axis, what is the smallest possible balance value?

#### Constraints

All points are distinct.

There does not exist a line that contains all points .

For all , .

#### Input Specification

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

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

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

#### Output Specification

Output lines, the answer to each query. Your output will be considered correct if the absolute or relative error of each value does not exceed .

#### 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 st and rd points:

For the second query, it is optimal to choose the line that passes through the rd and th 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 nd and rd points.

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