모바일 게임

휴대폰 온라인 게임이 인기를 끌자 당신도 경찰과 도둑 게임을 만들고 있다. 어떤 플레이어는 경찰을 조종하고, 다른 플레이어는 도둑을 조종한다. 경찰은 도둑을 잡는 것이 목표이고, 도둑은 도망치려 한다.

개발 중에 문제가 하나 생겼다. 휴대폰의 위치 갱신이 느려서 플레이어 위치를 1초에 한 번밖에 받지 못하기도 한다. 점수는 경찰이 도둑을 잡은 시각으로 매기므로 그 시각을 정확히 계산해야 한다.

경찰과 도둑은 게임 세계에서 직사각형으로 나타내고, 두 직사각형이 겹치면 경찰이 도둑을 잡은 것이다. 두 직사각형의 크기와 시각 0, 시각 1에서의 위치가 주어진다. 시각 0과 시각 1 사이에 두 직사각형이 겹치는 순간이 있는지 판정하고, 있다면 처음 겹치는 시각을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 두 줄이고, 각 줄에 정수 여섯 개가 있다.

첫 줄에는 $W_1$, $H_1$, $Xstart_1$, $Ystart_1$, $Xend_1$, $Yend_1$이 주어진다. $W_1$과 $H_1$은 경찰 직사각형의 너비와 높이다. $(Xstart_1, Ystart_1)$은 시각 0에서 경찰 직사각형의 왼쪽 위 꼭짓점이고, $(Xend_1, Yend_1)$은 시각 1에서의 왼쪽 위 꼭짓점이다.

둘째 줄에는 도둑에 대한 같은 값 $W_2$, $H_2$, $Xstart_2$, $Ystart_2$, $Xend_2$, $Yend_2$가 주어진다.

• $0 < T \le 100$
• $0 < W_i, H_i \le 100$
• $0 \le Xstart_i, Ystart_i, Xend_i, Yend_i \le 10000$
• 입력의 모든 값은 정수다.
• 좌표계는 $x$가 왼쪽에서 오른쪽으로, $y$가 위에서 아래로 커진다.
• 두 직사각형이 겹치거나, 변이나 꼭짓점만 닿아도 충돌이다.
• 경찰과 도둑은 각각 시각 0의 위치에서 시각 1의 위치까지 일정한 속력으로 직선을 따라 움직인다.

각 테스트 케이스마다 처음 충돌이 일어나는 시각을 한 줄에 출력한다. 이 값은 0 이상 1 이하다.

소수점 아래 일곱째 자리에서 반올림해 소수점 아래 여섯 자리까지 항상 출력한다. 즉 0.000000이나 1.000000처럼 자리를 채워 쓴다. 값이 정확히 절반이면 올림한다.

충돌이 없으면 No Collision을 출력한다.