가상의 우주에 있는 KOI 별에서 바라보는 밤하늘에는 밝게 빛나는 많은 별이 있다.

이 별에 살고있는 고등학생 나정보는 고정된 카메라로 매일 밤 자정에 하늘 사진을 찍고 있는데, 특이하게도 찍힌 별들은 2차원 평면의 정수 좌표로 항상 표현된다.

날마다 찍은 사진을 비교해 보니 어떤 별은 항상 같은 좌표에 있고, 어떤 별은 일정한 속도로 이동하고 있다.

이 때 별의 이동 속도는 [dx, dy] 로 표시되는데 dx 는 하루 동안의 x 축 좌표 변화량, dy 는 하루 동안의 y 축 좌표 변화량을 나타내며 역시 둘 다 정수이다.

당연하게도 각 별의 속도는 다른 별과 무관하고, 별들은 언제든 서로 겹칠 수 있다(단, 실제로 충돌하는 것은 아님). 이동하지 않는 별의 속도는 [0, 0]이다.

예를 들어, 아래 사진은 나정보가 처음(촬영일 0)으로 찍은 사진으로,별 A의 좌표는 (0, 0), 별 B의 좌표는 (5, 0), 그리고 별 C의 좌표는 (3, -3)이다.

다음 사진은 하루 뒤(촬영일 1)에 찍은 사진으로, 세 개의 별의 좌표가 (2, 0), (4, 0), 그리고 (4, -2)로 바뀌었다.

즉, 별 A의 속도는 [2, 0], 별 B의 속도는 [-1, 0], 별 C의 속도는 [1, 1]이다.

따라서 처음 사진을 찍은 날부터 이틀 뒤(촬영일 2)에 찍은 사진에서는 세 별의 좌표가 (4, 0), (3, 0), (5, -1)이 될 것이다.

나정보는 좌표 상에서 가장 멀리 떨어진 두 별의 거리를 매일 기록하고 있다.

두 별의 x좌표의 차이가 p이고 y좌표의 차이가 q인 두 별의 거리는 \sqrt{p^2 + q^2} 으로 정의한다.

예를 들어, 촬영일 0 의 사진에서 가장 멀리 떨어진 두 별은 별 A와 별 B이고 그 때 거리는 5 이며,촬영일 1 의 사진에서 가장 멀리 떨어진 두 별은 별 A와 별 C로 거리는 \sqrt{8} 이다.

별들의 초기 좌표와 속도, 마지막 촬영일이 주어졌을 때, 가장 멀리 떨어진 두 별의 거리가 최소인 촬영일과 그 때 거리의 제곱값을 구하는 프로그램을 작성하시오. 단, 이런 촬영일이 여러 날인 경우에는 그 중에서 가장 처음 찍은 촬영일을 구하시오.

앞의 예에서 마지막 촬영일이 3이라면, 각 촬영일의 최대 거리가 5(촬영일 0), \sqrt{8} (촬영일 1), \sqrt{5} (촬영일 2), 4(촬영일 3)가 되어 그 중 \sqrt{5} 가 최소이므로 촬영일 \sqrt[2]{5} 의 제곱값인 5 를 구하면 된다.

#3001 upload 549 done 107 how_to_reg 83

먼 별 timer 1s memory 256MB

#3001

먼 별 1s 256MB