Magical Towers

In a faraway kingdom there are \( n \) wizards. Each wizard owns two magical towers and he can teleport freely between his two towers. For mysterious reasons the residents want to live only in "safe" locations. A residence is considered safe if, for any direction in which a person moves from that residence, he will decrease his distance to at least one wizard (i.e. one of the wizard’s towers).

One can prove that the set of all safe residences forms a convex region. In fact, since each wizard may appear at either of his two towers, a person is safe if and only if for every unit vector \( v \) it holds that \[ v\cdot P < \max_{1\le i\le n}\;\max\Bigl\{v\cdot A_i,\; v\cdot B_i\Bigr\}, \] where \( A_i \) and \( B_i \) are the positions of the two towers of the \( i \)-th wizard and \( P \) is the position of the residence. Equivalently, the safe region is exactly the interior of the convex hull of all the \( 2n \) towers. Your task is to compute the area of that safe region.

Note: If the safe region degenerates (for example, when all towers lie on a line), its area is considered to be 0.

inputFormat

The first line contains an integer \( n \) (\(1 \le n \le 10^5\)), the number of wizards. Each of the next \( n \) lines contains four real numbers \( x_1, y_1, x_2, y_2 \) (\(|x_i|,|y_i| \le 10^9\)) which represent the coordinates of the two towers of a wizard.

outputFormat

Output a single real number: the area of the safe region. An answer is accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

1
0 0 1 0

0.0