시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB252068739823.676%

문제

가상의 우주에 있는 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}\)가 최소이므로 촬영일 2와 \(\sqrt{5}\) 의 제곱값인 5를 구하면 된다.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 별의 개수를 나타내는 정수 N (2 ≤ N ≤ 30,000)과 마지막 촬영일을 나타내는 정수 T (0 ≤ T ≤ 107)가 주어진다. 다음 N 개의 줄에 각 별의 좌표 (x, y)와 속도 [dx, dy]를 나타내는 네 개의 정수가 주어진다 (|x|, |y| ≤ 107이고 |dx|, |dy| ≤ 100). 이때 동일한 좌표의 별이 입력으로 들어올 수도 있다.

출력

표준 출력으로 다음 정보를 출력한다. 첫 번째 줄에는 가장 멀리 떨어진 두 별의 거리가 최소인 촬영일을 출력한다. 단, 이런 촬영일이 여럿 존재한다면 가장 빠른 촬영일을 출력한다. 두 번째 줄에는 그 때 거리의 제곱값을 정수로 출력한다.

서브태스크

번호배점제한
12

N = 2

240

2 ≤ N ≤ 1,000

339

T ≤ 20

419

원래의 제약조건 이외에 아무 제약조건이 없다.

예제 입력 1

3 3
0 0 2 0
5 0 -1 0
3 -3 1 1

예제 출력 1

2
5

예제 입력 2

2 1
-4 -2 2 1
4 2 -2 -1

예제 출력 2

1
20

채점 및 기타 정보

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