기하 문제

프로그래밍 대회의 기하 문제에 지친 당신은 대회를 떠나 게임 개발을 하기로 했다. 그런데 그곳에도 기하 문제가 기다리고 있었다. 당신은 두 명이 즐기는 2차원 아케이드 게임을 구상했다. 첫 번째 플레이어가 삼각형 금속 조각을 원하는 방향으로 던진다. 두 번째 플레이어는 그 조각을 맞히려고 다른 삼각형 금속 조각을 던진다. 두 조각이 충돌할지 알고 싶다.

두 번째 플레이어가 조각을 던지는 순간을 시각 0으로 하고, 두 조각의 위치와 속도를 저장한다. 게임에서는 시각 0에 두 조각이 이미 충돌해 있는 상태를 허용하지 않는다. 두 조각이 충돌하는 시각을 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄은 첫 번째 플레이어의 조각, 둘째 줄은 두 번째 플레이어의 조각을 설명한다. 각 설명은 공백으로 구분된 정수 8개 $x_1, y_1, x_2, y_2, x_3, y_3, v_x, v_y$로 이루어진다. $(x_i, y_i)$는 조각의 $i$번째 꼭짓점 위치이고, $v_x$와 $v_y$는 조각 속도의 x 성분과 y 성분이다.

각 테스트 케이스마다 두 조각이 충돌하는 가장 이른 시각을 한 줄에 출력한다. 답은 상대 오차 또는 절대 오차가 $10^{-9}$ 이하여야 한다. 두 조각이 끝까지 충돌하지 않으면 "NO COLLISION"(따옴표 제외)을 출력한다.

$1 \le T \le 100$

$-10^7 \le x_1, y_1, x_2, y_2, x_3, y_3, v_x, v_y \le 10^7$