A. Almost Aligned
time limit per test
6.4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A meteor shower is about to happen! As the enthusiastic astronomy photographer that you are, you want to take a single picture of all the meteors that will be part of the phenomenon. Not only that, you want to take the best possible picture. You know that the smaller the area of the photo, the better the picture. But how small can you make the picture to capture them all?

You can take a picture of any rectangular region of your camera's view, but you cannot rotate the camera. That is, your photo can be any axis-aligned rectangle. The challenge? The meteors are constantly moving. Think of time ($$$t$$$) as the number of seconds that have passed since the start of the meteor shower. Your goal is to find a non-negative value of $$$t$$$ at which you can capture every single meteor with the smallest possible rectangle. A photo captures all the meteors within the rectangle, including those on the border.

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$) indicating the number of meteors.

Each of the next $$$N$$$ lines describes a meteor with four integers $$$X$$$, $$$Y$$$, $$$V_X$$$ and $$$V_Y$$$ ($$$-10^9 \leq X, Y, V_X, V_Y \leq 10^9$$$), representing the location and velocity of the meteor, as seen by your camera. This means that at any time $$$t \ge 0$$$ the coordinates of the meteor are $$$(X + t \cdot V_X, Y + t \cdot V_Y)$$$. If $$$t<0$$$, the location of the meteor is undefined.

Output

Output a single line with the minimum area of an axis-aligned rectangle containing all the meteors at a time $$$t \ge 0$$$. The output must have an absolute or relative error of at most $$$10^{-9}$$$.

Examples
Input
4
0 0 10 10
0 0 10 10
10 10 -10 -10
10 0 -20 0
Output
22.222222222222222
Input
3
0 -1 0 2
1 1 1 1
-1 1 -1 1
Output
0.000000000000000
Input
3
0 -1 0 -2
1 1 1 1
-1 1 -1 1
Output
4.000000000000000
Input
1
0 0 0 0
Output
0.000000000000000