맥스웰의 악마

열역학 지식은 이 문제를 푸는 데 필요하지 않다.

맥스웰의 악마는 높이가 $h$이고 너비가 $2w$인 용기 안에 있다. 용기는 서로 맞닿은 두 칸으로 나뉘며, 각 칸의 높이는 $h$, 너비는 $w$이다. 두 칸 사이에는 통과할 수 없는 벽이 있고, 악마는 이 가운데 벽의 고정된 위치에 앉아 있다.

각 칸에는 입자가 들어 있다. 입자마다 위치, 속도, 색깔이 있다. 입자가 칸의 벽에 부딪히면 완전 탄성으로 반사된다. 그림 H.1은 입자 두 개가 든 용기를 보여 준다. 왼쪽 칸에는 파란 입자, 오른쪽 칸에는 빨간 입자가 있다.

그림 H.1: 첫 번째 예제의 입력. 악마는 회색으로 확대해 그렸지만, 실제로는 무한히 작고 얼굴도 없다.

맥스웰의 악마는 입자를 분류해 엔트로피를 줄이려 한다. 빨간 입자는 모두 왼쪽 칸에, 파란 입자는 모두 오른쪽 칸에 있어야 한다. 이를 위해 악마는 입자가 자기 위치에 부딪힐 때 중앙 벽을 통과시킬 수 있다.

칸의 바닥은 $x$축 위에 놓여 있고, 중앙 벽은 양의 $y$축을 따라 놓여 있다. 악마가 정한 임의의 시각에 악마의 위치 $(0, d)$에 있는 모든 입자는 벽에 반사되지 않고 속도를 유지한 채 반대편 칸으로 넘어갈 수 있다. 악마는 이 작업을 원하는 때에 원하는 만큼 몇 번이고 할 수 있다. 입자가 악마의 위치에 부딪혀도 통과시키지 않을 수 있다. 다만 여러 입자가 같은 순간 $(0, d)$에 있으면, 이들은 모두 통과하거나 모두 반사된다.

악마가 입자를 분류하도록 도와라. 빨간 입자가 모두 왼쪽 칸에, 파란 입자가 모두 오른쪽 칸에 있게 되는 가장 이른 시각은 언제인가?

첫 줄에 다섯 정수 $w$, $h$, $d$, $r$, $b$가 주어진다. $w$와 $h$($2 ≤ w, h ≤ 200$)는 각 칸의 너비와 높이이다. $d$($0 ≤ d ≤ h$)는 중앙 벽에서 악마 위치의 $y$좌표이다. $r$과 $b$($0 ≤ r, b$이고 $1 ≤ r + b ≤ 200$)는 각각 빨간 입자와 파란 입자의 개수이다.

이어서 $r + b$개의 줄에 입자마다 정수 네 개 $p\_x$, $p\_y$, $v\_x$, $v\_y$가 주어진다. $(p\_x, p\_y)$($0 < |p\_x| < w$, $0 < p\_y < h$)는 초기 위치이고, $(v\_x, v\_y)$($|v\_x| < w$, $|v\_y| < h$, $(v\_x, v\_y) \ne (0, 0)$)는 초기 속도이다. 앞의 $r$개 입자는 빨간 입자이고, 나머지는 파란 입자이다.

빨간 입자가 모두 왼쪽 칸에, 파란 입자가 모두 오른쪽 칸에 있게 되는 데 필요한 최소 시간을 출력한다. 답은 절대 오차 또는 상대 오차가 $10^{-6}$ 이하여야 한다. 유한한 시간 안에 이 상태가 될 수 없으면 impossible을 출력한다.