405861: GYM102136 C Kingdom Partition

Recently, King of Bandiaterra Barbato started thinking how to split his kingdom between two sons Philip and Ferdinand. Barbato's property can be represented by N castles, which can be denoted as integer coordinate points (X_i, Y_i). Since, king equally loves his sons, he decided to perform the partition according to the Bandiaterra Fairness Code.

To perform the separation, straight line parallel to Y-axis should be drawn. This line contains point (X, 0). Castles located on the west of the border line (X_i ≤ X) will be inherited by Philip and the ones on the east (X < X_i) – to Ferdinand. Eventually, each brother will have a city, which can be represented as a convex hull of castles inherited by Philip and Ferdinand, accordingly. According to the Bandiaterra Fairness Code, partition is more fair if absolute value of difference between Philip's and Ferdinand's city areas is as close as possible to S – sacral number of Bandiaterra.

Barbato conducted Bandiaterra's council of elders to decide on exact location of the border line and record it to his testament.

First line contains two integer numbers N and S — number of castles and sacral number, accordingly.

Next N lines each contain two integer numbers X_i and Y_i — coordinates of each castle. There are no castles with same coordinates. Area of an empty city which has no castles is zero.

Single line should contain one number — absolute value between city areas, which is as close as possible to the sacral number of Bandiaterra. If there is more than one possible border lines, output that, which makes absolute difference between city areas as low as possible. Absolute and relative error of your answer should not exceed 10^- 4.

9 31
8 5
-3 1
1 -1
-4 -3
-2 -9
3 -4
9 0
1 7
-7 2

42.0000