CodePSU 2019 - Advanced


2019-03-24 09:15 AKDT

CodePSU 2019 - Advanced


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


Time remaining


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}


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 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
1 9 3 2
2 5 2 3
6 7 3 4