Informatica Online Judge

  먼 별 #3 [1829 / 0725]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 7   Total Tried : 8


The Champion of this Problem (C++) : gs16024 - 0ms / 2535byte
My Best Submission (C++) : N/A

[KOI2017_H_4]

Background

가상의 우주에 있는 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인 두 별의 거리는 √p^2+q^2으로 정의한다.

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

별들의 초기 좌표와 속도, 마지막 촬영일이 주어 졌을 때, 가장 멀리 떨어진 두 별의 거리가 최소 인 촬영일과 그 때 거리의 제곱값을 구하는 프로그램을 작성하시오.

단, 이런 촬영일이 여러 날인 경우에는 그 중에서 가장 처음 찍은 촬영일을 구하시오.

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

Input

첫 번째 줄 에는 별의 개수를 나타내는 정수 N (2≤N≤30,000)과 마지막 촬영일을 나타내는 정수 T (0≤T≤10^7)가 주어진다.

다음 N개의 줄에 각 별의 좌표 (x,y)와 속도 [dx,dy]를 나타내는 네 개의 정수가 주어진다. (|x|,|y|≤10^7 이고 |dx|,|dy|≤100).

이때 동일한 좌표의 별이 입력으로 들어올 수도 있다.

[Sub-Task Info]
#1 : N = 2 (2pts)
#2 : 2 <= N <= 1,000 (40pts)
#3 : T <= 20 (39pts)
#4 : 추가제한사항은 없다. (19pts)

Output

첫 번째 줄 에는 가장 멀리 떨어진 두 별의 거리가 최소인 촬영일을 출력한다.

단, 이런 촬영일이 여럿 존재한 다면 가장 빠른 촬영일을 출력한다.

두 번째 줄에 는 그 때 거리의 제곱값을 정수로 출력한다.

IO Example

입력
3 3
0 0 2 0
5 0 -1 0
3 -3 1 1

출력
2
5

입력2
2 1
-4 -2 2 1
4 2 -2 -1

출력2
1
20

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]