백준 31536 (C++) 멈뭄미믜 저주 탈출

최초 업로드: 2025-08-06 23:29:50

최근 수정 시간: 2025-08-06 23:30:14

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] 멈뭄미믜 저주 탈출

[문제 링크](https://www.acmicpc.net/problem/31536)

## 문제 설명

지난 두 대회에서 섯섯시싀 저주에 걸리고 풀어낸 현철이는 다음으로 멈뭄미믜 저주를 풀어내야 한다.

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$좌표의 값을 공백으로 구분하여 출력한다.

가능한 답이 여러 개라면 아무거나 하나 출력한다.

## 풀이
#### 사각형 겉표면만 살펴보면 됩니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int outsideM[4004], outsideK[4004]; // left right up down

ll getCost(ll x1, ll x2, ll y1, ll y2) {
    return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int Mx, My, a, Kx, Ky, b, M, K; cin >> Mx >> My >> a >> Kx >> Ky >> b >> M >> K;
    a++; b++;

fill(outsideM, outsideM+a, INF);
    fill(outsideM+a, outsideM+3*a, -INF);
    fill(outsideM+3*a, outsideM+4*a, INF);
    while(M--) {
        int x, y; cin >> x >> y;
        outsideM[x-Mx] = min(outsideM[x-Mx], y);
        outsideM[x-Mx+a] = max(outsideM[x-Mx+a], y);
        outsideM[y-My+2*a] = max(outsideM[y-My+2*a], x);
        outsideM[y-My+3*a] = min(outsideM[y-My+3*a], x);
    }

fill(outsideK, outsideK+b, INF);
    fill(outsideK+b, outsideK+3*b, -INF);
    fill(outsideK+3*b, outsideK+4*b, INF);
    while(K--) {
        int x, y; cin >> x >> y;
        outsideK[x-Kx] = min(outsideK[x-Kx], y);
        outsideK[x-Kx+b] = max(outsideK[x-Kx+b], y);
        outsideK[y-Ky+2*b] = max(outsideK[y-Ky+2*b], x);
        outsideK[y-Ky+3*b] = min(outsideK[y-Ky+3*b], x);
    }

ll minCost = LINF;
 int resX1, resX2, resY1, resY2;
 for(int i=0;i<4*a;i++) {
 for(int j=0;j<4*b;j++) {
 if(outsideM[i]==INF || outsideM[i]==-INF || outsideK[j]==INF || outsideK[j]==-INF) continue;
 int x1, y1, x2, y2;
 if(i<2*a) {
 x1 = i%a+Mx;
 y1 = outsideM[i];
 } else {
 x1 = outsideM[i];
 y1 = i%a+My;
 }
 if(j<2*b) {
 x2 = j%b+Kx;
 y2 = outsideK[j];
 } else {
 x2 = outsideK[j];
 y2 = j%b+Ky;
 }
 ll cost = getCost(x1, x2, y1, y2);
 if(minCost>cost) {
 minCost = cost;
 resX1 = x1;
 resX2 = x2;
 resY1 = y1;
 resY2 = y2;
 }
 }
 }
 cout << minCost << '\n' << resX1 << ' ' << resY1 << '\n' << resX2 << ' ' << resY2;
}
```