31536번 - 멈뭄미믜 저주 탈출 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 282 | 57 | 43 | 25.904% |
문제
지난 두 대회에서 섯섯시싀 저주에 걸리고 풀어낸 현철이는 다음으로 멈뭄미믜 저주를 풀어내야 한다.
2차원 평면에 위치한 멈뭄미 나라에는 Mat마을과 Kor마을이 있다. 두 마을은 멈뭄미 나라의 마을에 걸맞게 경계가 정사각형 모양이며, 마을의 경계는 $x$축 혹은 $y$축에 평행하다. 또한, 두 마을은 경계를 포함해 서로 어떠한 점에서도 만나지 않는다.
각 마을에는 몇 개의 우체국이 마을의 경계 혹은 마을 내부에 있다. 또한 두 우체국을 골라 연결할 수 있는데, 두 우체국을 연결하는 데 드는 비용은 두 우체국 간 거리의 제곱이다.
현철이는 멈뭄미믜 저주를 풀기 위해 Mat마을과 Kor마을에서 우체국을 하나씩 골라 연결해야 하는데, 이 비용을 최소로 하려고 한다. 현철이를 도와 각 마을에서 어떤 우체국을 연결해야 하는지 정해보자.
입력
첫 번째 줄에 Mat마을의 왼쪽 아래 점의 좌표 $M_x, M_y$와 경계의 한 변의 길이 $a$가 공백으로 구분되어 주어진다. $(1\le a\le 1\, 000;$ $-10^6\le M_x,M_y\le 10^6-a)$
두 번째 줄에 Kor마을의 왼쪽 아래 점의 좌표 $K_x, K_y$와 경계의 한 변의 길이 $b$가 공백으로 구분되어 주어진다. $(1\le b\le 1\, 000;$ $-10^6\le K_x,K_y\le 10^6-b)$
세 번째 줄에 Mat마을에 있는 우체국의 개수 $M$과 Kor마을에 있는 우체국의 개수 $K$가 공백으로 구분되어 주어진다. $(1\le M\le(a+1)^2;$ $1\le K\le(b+1)^2)$
다음 $M$개 줄에 걸쳐 Mat마을에 있는 우체국의 좌표들이 한 줄에 하나씩 $x$좌표와 $y$좌표의 값이 공백으로 구분되어 주어진다.
다음 $K$개 줄에 걸쳐 Kor마을에 있는 우체국의 좌표들이 한 줄에 하나씩 $x$좌표와 $y$좌표의 값이 공백으로 구분되어 주어진다.
모든 주어지는 입력은 정수이며, 두 마을은 경계를 포함해 서로 어떠한 점에서도 만나지 않는다. 또한 모든 우체국의 좌표는 서로 다른 격자점이며 이는 해당 우체국이 속한 마을의 경계 혹은 내부에 있다.
출력
첫 번째 줄에 두 마을의 우체국을 하나씩 골라 연결할 때 드는 비용의 최솟값을 출력한다.
두 번째 줄에 Mat마을에서 고른 우체국의 $x$좌표와 $y$좌표의 값을 공백으로 구분하여 출력한다.
세 번째 줄에 Kor마을에서 고른 우체국의 $x$좌표와 $y$좌표의 값을 공백으로 구분하여 출력한다.
가능한 답이 여러 개라면 아무거나 하나 출력한다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $M=K=1$ |
| 2 | 22 | $a, b \le 50$ |
| 3 | 30 | $M=(a+1)^2;$ $K=(b+1)^2$ |
| 4 | 58 | 추가적인 제한 조건 없음 |
예제 입력 1
12 13 4 27 10 7 1 1 15 14 28 12
예제 출력 1
173 15 14 28 12
아래 그림은 비용이 최소가 되도록 두 우체국을 고른 경우이다. 구체적으로 각 마을에서 고를 수 있는 우체국은 하나씩 있으므로 Mat마을은 $(15,14)$, Kor마을은 $(28,12)$를 골라서 답은 $(15-28)^{2}+(14-12)^{2}=173$이다.
예제 입력 2
0 0 54 13 64 63 9 8 9 3 27 7 49 21 38 42 21 45 4 35 31 25 18 29 21 18 25 81 41 75 61 93 57 103 38 111 22 97 53 94 31 85
예제 출력 2
1098 38 42 41 75
아래 그림은 비용이 최소가 되도록 두 우체국을 고른 경우이다. 구체적으로 Mat마을은 $(38,42)$, Kor마을은 $(41,75)$를 골라서 답은 $(38-41)^{2}+(42-75)^{2}=1098$이다.
예제 입력 3
1 5 1 4 8 2 4 9 1 6 2 5 1 5 2 6 6 10 5 8 4 10 4 9 6 8 5 10 5 9 6 9 4 8
예제 출력 3
8 2 6 4 8
아래 그림은 비용이 최소가 되도록 두 우체국을 고른 경우이다. 구체적으로 Mat마을은 $(2,6)$, Kor마을은 $(4,8)$를 골라서 답은 $(2-4)^{2}+(6-8)^{2}=8$이다.
출처
University > 고려대학교 > MatKor Cup > 제4회 고려대학교 MatKor Cup: 2024 Winter/Spring D번
- 문제를 만든 사람: alex04, finimage, kidw0124
- 문제를 번역한 사람: tikiliki0417
- 문제를 검수한 사람: coo001, devluyten, eoaud0108, sshs29hanul, tlsdydaud1, utilforever, yijw0930
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호