시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 7 5 3 60.000%

문제

You have a radio receiver and want to receive N messages. Each message is transmitted at a predetermined time measured in seconds since the epoch. Also each message is transmitted from a predetermined position representing the displacement in meters from the origin (you are in 1-dimensional space). Your radio is capable of receiving any message that is transmitted no farther than D meters from your current position, where Dis a nonnegative real number.

You can start at any position of your choice and move at the rate of at most one meter per second. The action of receiving a message itself takes no time. Your task is to find the smallest D that allows you to get all messages.

입력

The first line of input gives the number of test cases, CC test cases follow. For each test case there will be:

  • One line containing the integer N, the number of messages.
  • N lines corresponding to the N messages where each of them contains 2 integers P and T separated by one space. P is the position where the message is transmitted from and T is the time when this message is transmitted (The messages will have distinct transmission times).

Limits

  • 1 ≤ C ≤ 100
  • 1 ≤ N ≤ 1000
  • 0 ≤ P ≤ 109
  • 0 ≤ T ≤ 109
 

 

출력

For each test case, output one line containing "Case #x: ", where x is the number of the test case, followed by the minimum value D that allows you to get all messages. Answers with a relative or absolute error of at most 10-9 will be considered correct.

예제 입력 1

3
3
7 2
20 3
0 11
2
6 5
6 3
4
5 3
2 1
9 4
7 2

예제 출력 1

Case #1: 6
Case #2: 0
Case #3: 2.00

힌트

Here is one possible scenario with D = 6 for test case #1. Start at position 13 and time 2 to get message 0. Then walk to the right to position 14, arriving at time 3 to get message 1. Then walk left to position 6, arriving at time 11 to get message 2.

채점

  • 예제는 채점하지 않는다.