2209번: 버스 터미널

https://www.acmicpc.net/problem/2209

n^3 풀이로 발적화

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX_N = 5e2;
int n, w[MAX_N][MAX_N], x[MAX_N], y[MAX_N], res = 0x7fffffff, ck[MAX_N];
pair<int, int> p[MAX_N], a[MAX_N], b[MAX_N];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", x + i, y + i);
        for (int j = 0; j < i; j++) w[i][j] = w[j][i] = abs(x[i] - x[j]) + abs(y[i] - y[j]);
        a[i] = { x[i] + y[i],i };
        b[i] = { x[i] - y[i],i };
    }
    sort(a, a + n);
    sort(b, b + n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            fill(ck, ck + n, 0);
            int m1 = 0, m2 = 0, h1 = 0, t1 = n - 1, h2 = 0, t2 = n - 1, pcnt = 0;
            while (h1 <= t1) {
                int maxi = max({ w[i][a[h1].second],w[i][a[t1].second],w[i][b[h2].second],w[i][b[t2].second] });
                if (maxi == w[i][a[h1].second]) p[pcnt++] = { w[i][a[h1].second],a[h1].second }, ck[a[h1++].second] = 1;
                else if (maxi == w[i][a[t1].second]) p[pcnt++] = { w[i][a[t1].second],a[t1].second }, ck[a[t1--].second] = 1;
                else if (maxi == w[i][b[h2].second]) p[pcnt++] = { w[i][b[h2].second],b[h2].second }, ck[b[h2++].second] = 1;
                else if (maxi == w[i][b[t2].second]) p[pcnt++] = { w[i][b[t2].second],b[t2].second }, ck[b[t2--].second] = 1;
                while (h1 <= t1 && ck[a[h1].second]) h1++;
                while (h1 <= t1 && ck[a[t1].second]) t1--;
                while (h2 <= t2 && ck[b[h2].second]) h2++;
                while (h2 <= t2 && ck[b[t2].second]) t2--;
            }
            for (int k = 0; k <n - 1; k++) {
                res = min(res, max({ p[k].first + p[k + 1].first,m1 + m2,p[k].first + w[i][j] + m1 }));
                m2 = max(m2, w[j][p[k].second]);
                if (m1 < m2) swap(m1, m2);
            }
        }
    }
    printf("%d", res);
    return 0;
}