Maxwell’s Demon

Relax: No knowledge of thermodynamics is needed to solve this problem.

Maxwell’s demon sits in a container of height h and width 2w. The container is divided into two adjacent chambers, each of height h and width w. An impenetrable wall separates the two chambers, and the demon sits at a fixed position on this center wall.

The chambers contain particles, each particle having a position, a velocity, and a color. When a particle strikes the wall of a chamber, it reflects off the wall with perfect elasticity. Figure H.1 shows a container with two particles, a blue one in the left chamber and a red one in the right chamber.

Figure H.1: The first sample input. The demon is shown enlarged in gray, while in reality it is infinitesimally small (and does not have a face).

Maxwell’s demon seeks to reduce entropy by sorting the particles. It wants all red particles to be in the left chamber and all blue particles to be in the right chamber. To achieve this, it has a special power: it can allow particles to pass through the center wall when they hit the demon’s position.

The chamber bottoms lie on the x-axis, and their dividing center wall runs along the positive y-axis. At any time of the demon’s choosing, all particles at the demon’s position (0,d) will not reflect off the center wall but will instead pass through to the other chamber, maintaining their velocity. The demon can do this whenever and as often as it wants and can also choose not to allow a particle through even though it hits the demon’s position. However, if multiple particles are at position (0,d) simultaneously, either all such particles pass through the center wall or all particles are reflected.

Help the demon sort the particles and reduce entropy! What is the earliest time when it is possible for all red particles to be in the left chamber and all blue particles to be in the right chamber?

Entrada

The first line consists of five integers w, h, d, r, b, where w and h (2≤w,h≤200) are the width and the height of each chamber, d (0≤d≤h) is the y-coordinate of the demon’s position on the container’s center wall, and r and b (0≤r,b and 1≤r+b≤200) are the number of red and blue particles, respectively.

This is followed by r+b lines, each describing a single particle using four integers p_x, p_y, v_x, v_y, where (p_x, p_y) (0 < |p_x| < w, 0 < p_y < h) is the initial position of the particle, and (v_x, v_y) (|v_x| < w, |v_y| < h, (v_x, v_y) \ne (0, 0)) is the initial velocity of the particle. The first r particles described are red while the remaining are blue.

Salida

Output the least amount of time needed for all red particles to be in the left chamber and all blue particles to be in the right chamber. Your answer should have an absolute or relative error of at most 10^{-6}. If it is impossible for all red particles to be in the left chamber and all blue particles to be in the right chamber within a finite amount of time, output impossible.

Ejemplo #1

Ejemplo #2

Fuente

#8523
Juez especial

Calificación en espera

Maxwell’s Demon 2s 1024MB

Problemas

Entrada

Salida

Ejemplo #1

Ejemplo #2

Fuente

#8523 upload - done - how_to_reg - auto_awesome Juez especial stop_circle Calificación en espera

Maxwell’s Demon timer 2s memory 1024MB

Problemas translate English text_fields

Entrada

Salida

Ejemplo #1

Ejemplo #2

Fuente

Enlaces entrantes Solo conjuntos de problemas oficiales

#8523
Juez especial

Calificación en espera

Maxwell’s Demon 2s 1024MB

Problemas