CodePSU 2019 - Advanced

Start

2019-03-24 09:15 AKDT

CodePSU 2019 - Advanced

End

2019-03-24 13:15 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -671 days 4:00:24

Time elapsed

4:00:00

Time remaining

0:00:00

Problem G
Minimum Crime Area

I do declare… There has been a murder. You have been hired as the detective on the case and as you arrive on the crime scene there is evidence scattered everywhere. In order to make sure that none of the evidence gets tampered with, your job is to outline the entire crime scene in “do not cross” tape. You’ll be given the current state of the crime scene in the form of a bunch of rectangular-shaped objects that represent the pieces of evidence. You must lay out the tape such that it forms a convex polygon that surrounds all of the shapes and minimizes the area (see diagram below). Then, return the (Minimum Crime) Area that the tape surrounds.

\includegraphics[width=0.2\textwidth ]{MCAdiagram}

Input

The first line of input is a number, $n$ ($1 \leq n \leq 1\, 000$), representing the number of items of evidence. Then, the following $n$ lines of input are formatted as $x$ $y$ $l$ $w$. Where $x$ and $y$ ($1 \leq x, y \leq 100\, 000$) represent the coordinates of the top left corner of the rectangle and $l$ and $w$ ($0 \leq l,w \leq 1\, 000$) represent the length and width of each rectangle.

Output

Output a real number representing the Minimum Crime Area as specified above. Your answer should have exactly one digit after the decimal point.

Sample Input 1 Sample Output 1
3
1 9 3 2
2 5 2 3
6 7 3 4
46.0