먼 별 > 문제은행

본문 바로가기


문제은행

3001 : 먼 별

제한시간: 1Sec    메모리제한: 64mb
해결횟수: 5회    시도횟수: 62회   



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

날마다 찍은 사진을 비교해 보니 어떤 별은 항상 같은 좌표에 있고, 어떤 별은 일정한 속도로 이동하고 있다. 이 때 별의 이동 속도는 [dx, dy] 로 표시되는데 dx 는 하루 동안의 x 축 좌표 변화량, dy 는 하루 동안의 y 축 좌표 변화량을 나타내며 역시 둘 다 정수이다.

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

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

a7d74ddb05a6de6c603cb8618c4b6b09_1471002

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

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

나정보는 좌표 상에서 가장 멀리 떨어진 두 별의 거리를 매일 기록하고 있다. 두 별의 ​ 좌표의 차이가 ​ 이고 ​ 좌표의 차이가 ​ 인 두 별의 거리는 a7d74ddb05a6de6c603cb8618c4b6b09_1471002으로 정의한다. 예를 들어, 촬영일 0 의 사진에서 가장 멀리 떨어진 두 별은 별 A와 별 B이고 그 때 거리는 5 이며, 촬영일 1 의 사진에서 가장 멀리 떨어진 두 별은 별 A와 별 C로 거리는 a7d74ddb05a6de6c603cb8618c4b6b09_1471002이다.

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

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

 


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


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

부분문제의 제약 조건
• 부분문제 1: 전체 점수 100점 중 2점에 해당하며 N = 2 이다.
• 부분문제 2: 전체 점수 100점 중 40점에 해당하며 2 ≤ N ≤ 1,000 이다.
• 부분문제 3: 전체 점수 100점 중 39점에 해당하며 T ≤ 20 이다.
• 부분문제 4: 전체 점수 100점 중 19점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.

[Copy]
3 3
0 0 2 0
5 0 -1 0
3 -3 1 1
[Copy]
2
5


[Copy]
2 1
-4 -2 2 1
4 2 -2 -1
[Copy]
1
20




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.