Page not loading? Try clicking here.
Placeholder

#6346
Special judge

Almost Aligned 1.5s 1024MB

Problems

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 ≤ N ≤ 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 ≤ X, Y, V_X, V_Y ≤ 10^9), representing the location and velocity of the meteor, as seen by your camera. This means that at any time t ≥ 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 ≥ 0. The output must have an absolute or relative error of at most 10^{-9}.


Example #1

4
0 0 10 10
0 0 10 10
10 10 -10 -10
10 0 -20 0
22.2222222222222

Example #2

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

Example #3

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

Example #4

1
0 0 0 0
0

Source

The 2024 ICPC Latin America Championship A번

You must sign in to write code.