31751번 - Almost Aligned 스페셜 저지다국어

문제

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.

입력

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 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}$.

제한

힌트