동기모임

동기모임

봄철을 맞아 종현이는 동기들과 동기모임을 진행하려고 한다. N명의 동기들은 “S로” 라는 일직선 대로위에 거주하고 있다. 따라서 모임장소도 “S로”중 한군데에서 만나려고 한다. 동기들은 각각 이동할 수 있는 최대속도가 주어지며 동기들은 한번 출발하면 일정한 속도와 일정한 방향으로 목적지를 향해 이동한다. 종현이는 동기모임을 빨리 진행하고 싶기 때문에 최대한 빠른시간에 모든 동기들이 모일 수 있는 장소를 결정하고 싶다. “S”로를 수평선이라 가정했을 때 가장 빠른시간에 동기모임을 할 수 있는 시간을 출력하는 프로그램을 작성하시오.

 

[제한사항]

1. 각 동기들은 한번 출발하면 일정한 방향과 속도로 목적지 까지 이동한다. 즉, 방향이나 속도를 변화시킬 수 없다.

2. 각 동기들의 처음 위치와 최대 속도는 정수로 주어진다.

3. 만날 수 있는 가장 빠른 시간은 소수점 7자리에서 반올림하여 소수점 6자리의 값으로 출력한다.

 

[입력]

최초 테스트케이스의 개수 T가 주어지며, 다음 줄부터 T개의 테스트 케이스가 주어진다. 각 테스트 케이스마다 첫 줄에는 동기의 수 N(2 ≤ N ≤ 100,000)이 주어지고, 그 다음줄엔 1번 동기부터 N번 동기까지의 현재 위치인 X_i (-1,000,000,000 ≤ X_i ≤ 1,000,000,000)가 각각 공백을 두고 주어진다. 그 다음 줄엔 1번 동기부터 N번동기까지의 최대속도(1초당 이동할 수 있는 거리, 1 ≤ V_i ≤ 100,000,000)가 공백을 두고 주어진다. 각 위치와 최대속도 X_i V_i는 정수로 주어진다.

 

[출력]

각각의 테스트 케이스에 대하여 #x (x는 테스트 케이스 번호, 1부터 시작)을 출력하고 공백을 하나 둔 다음 가장 빨리 만날 수 있는 시간을 출력한다. 시간은 소수점 7자리에서 반올림 한 값을 출력하도록 한다.

 

[입출력예제]

입력

3

3

7 1 3

1 2 1

4

5 10 3 2

2 3 2 4

2

4 5

10 8

 

출력

#1 2.000000

#2 1.400000

#3 0.055556