Asia Hong Kong Regional Contest 2016

#### Start

2016-11-06 02:00 UTC

## Asia Hong Kong Regional Contest 2016

#### End

2016-11-06 07:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -767 days 7:26:25

5:00:00

0:00:00

# Problem EPeak Tower

After taking the Peak Tram, you reach the Peak Tower — an ideal place to take a picture of the Victoria Harbour.

Being a must-see attraction, the Peak Tower is packed with tourists, and it’s pretty hard to take a picture without many people blocking the beautiful scene. Occasionally birds are flying around as well. You are wondering: how to take the best picture to minimise the area blocked by tourists and birds?

You are taking a picture to capture a scene of width $W$ and height $H$ (both in metres). The bottem left corner of the scene are at coordinates $(0,0)$. Each tourist or bird can be modelled as an axis-aligned rectangle that moves at a constant velocity.

In the above example there are three tourists (red, blue, and orange) and a bird (dark green). You want to minimise the area of the union of these rectangles.

Each tourist or bird can be represented by a rectangle of width $w$ and height $h$ (both in metres). Its motion is described by:

• $s_ x$: The initial x-coordinate of its bottom left corner (at time $t = 0$).

• $s_ y$: The initial y-coordinate of its bottom left corner (at time $t = 0$).

• $v_ x$: The horizontal velocity in $\mathrm{m/s}$ at which it moves (positive if it’s moving rightwards).

• $v_ y$: The vertical velocity in $\mathrm{m/s}$ at which it moves (positive if it’s moving upwards).

Obviously the best picture you can take is to wait until all objects are gone. However, you have a tight schedule and must take the picture within $E$ seconds. Given the information about the motion of the $N$ objects, when should you take the picture to minimise the area blocked by them?

## Input

The first line consists of an integer $N$ ($0 \leq N \leq 50$). The second line consists of $3$ real numbers $W$, $H$, $E$ ($0 < W, H \leq 300$, $0 < E \leq 100$). Each of the following $N$ lines consists of $6$ real numbers $w$, $h$, $s_ x$, $s_ y$, $v_ x$, $v_ y$, representing the size (in metres) and motion (in $\mathrm{m/s}$) of the $i$th object ($0 < w,h \leq 100$, $-300 \leq s_ x, s_ y, v_ x, v_ y \leq 300$). Each real number has at most $6$ digits past the decimal point.

## Output

Output a number to indicate the minimal possible total area blocked by tourists and birds. Any solution with an absolute or relative error within $10^{-6}$ will be accepted.

Sample Input 1 Sample Output 1
0
300.0 200.0 6.0

0.0

Sample Input 2 Sample Output 2
2
270.0 200.0 10.0
15.0 20.0 125.0 0.0 10.0 0.0
15.0 15.0 240.0 0.0 -10.0 0.0

300.0