Asia Hong Kong Regional Contest 2016

Start

2016-11-06 03:00 CET

Asia Hong Kong Regional Contest 2016

End

2016-11-06 08:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -617 days 2:26:07

Time elapsed

5:00:00

Time remaining

0:00:00

Problem E
Peak 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.

\includegraphics[width=.6\textwidth ]{scene}

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{ms}^{-1}$ at which it moves (positive if it’s moving rightwards).

  • $v_ y$: The vertical velocity in $\mathrm{ms}^{-1}$ 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 floating point numbers $W$, $H$, $E$ ($0 < W, H \leq 300$, $0 < E \leq 100$). Each of the following $N$ lines consists of 6 floating point numbers $w$, $h$, $s_ x$, $s_ y$, $v_ x$, $v_ y$, representing the size and motion of the $i$th object ($0 < w,h \leq 100$, $-300 \leq s_ x, s_ y, v_ x, v_ y \leq 300$). Each floating point number has at most $6$ decimal places.

Output

Output a floating point 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