시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 4 3 3 75.000%

문제

Online gaming using mobile phones has exploded in popularity, and you’ve thrown yourself on the wave, now creating a kind of cop-and-robber type of game. Some players control the cops, while others control the robbers. The objective for the cop players is to catch the robbers, while the robbers will try to escape. During development, you’ve recently encountered a problem. There is a significant lag in the update rate on the mobile phones. You might get updates on player positions as seldom as once every second. Since scoring is based on when the cops caught the robbers, you need to calculate this exact time.

Cops and robbers are modeled as rectangles in the game world, and a cop has caught a robber if their rectangles overlap. You are given the sizes of the rectangles, as well as their positions in time 0 and 1. Your program should calculate whether the rectangles have overlapped at some point in this time interval and, if so, at what time this happened for the first time (clarification).

입력

The first line of input contains a single number T, the number of test cases to follow. Each test case consists of two lines, containing 6 numbers each. The first line contains the integers W1, H1, Xstart1, Ystart1, Xend1 and Yend1. W and H describe the width and height of the policeman rectangle, respectively. Xstart1 and Ystart1 describe the policeman’s starting point (the upper left corner), while Xend1 and Yend1 describe his end point (his location at time 1). The second line contains six integers W2, H2, Xstart2, Ystart2, Xend2 and Yend2, the corresponding numbers for the robber.

  • 0 < T ≤ 100
  • 0 < Wi, Hi ≤ 100
  • 0 ≤ Xstarti, Ystarti, Xendi, Yendi ≤ 10000
  • The coordinate system has increasing x-values from left to right, and increasing y-values from top to bottom.
  • A collision occurs if the two rectangles overlap or if their sides/corners touch.
  • Assume that both the cop and robber moved in a straight line.
  • An absolute or relative error of up to 10−7 compared to the correct answer will be accepted.

출력

For each test case, output one line containing a single number, the earliest (clarification) instant in time (a real number between 0 and 1, inclusive) in which a collision occurs. If there is no collision, output No Collision instead.

예제 입력

3
2 2 0 0 0 8
2 2 2 10 2 2
5 5 10 10 0 0
1 4 0 0 10 0
4 4 3 9 10 18
3 3 8 14 15 23

예제 출력

0.5
0.6
No Collision

힌트