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?
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 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 |