13421번: 국민 랜드

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


"국민 랜드는 한 변의 길이가 1 이상인 정사각형......


$O(1)$

정사각형 길이가 2s 이라면 네 꼭지점 좌표는 (-s,-s), (-s,s), (s,-s), (s,s)가 된다.
기존의 네 점 (ai,bi)를 위 네 점과 대응시키는 4!의 경우가 존재한다.
모든 경우에 대해 가장 작은 비용의 최대 크기 정사각형을 찾자.
대응 관계가 정해졌을 때 s관한 비용의 함수 f(s)는

|-s-a1|+|-s-b1|+
|-s-a2|+|s-b2|+
|s-a3|+|-s-b3|+
|s-a4|+|s-b4|
가 되며 s=(A={-a1,-b1,-a2,b2,a3,-b3,a4,b4}의 중앙값) 일 때 함숫값이 최소가 된다.
최소 비용 중 최대 크기 정사각형을 구해야 하므로 정렬한 A의 원소 중 5번째 값을 s의 후보로 놓는다.
s가 음수가 될 수도 있는데 -s도 존재하므로 최소 비용 상의 최대 s값을 취하면 상관없다.
답은 2s이다.

네 점이 모두 원점에 있을 경우 s=0이 나올 것이다. 이 때는 문제 조건에 따라 1을 출력한다.

#include<cstdio>
#include<algorithm>
using namespace std;
pair<int, int> p[4];
long long mini = 8e9;
int r, a[8];
int main() {
    for (int i = 0; i<4; i++) scanf("%d%d", &p[i].first, &p[i].second);
    sort(p, p + 4);
    do {
        for (int i = 0; i < 4; i++)
            a[i] = p[i].first*(1 - i / 2 % 2 * 2),
            a[i + 4] = p[i].second*(1 - i % 2 * 2);
        sort(a, a + 8);
        long long s = 0;
        for (int i = 0; i < 8; i++) s += abs(a[i] - a[4]);
        if (s<mini || s == mini&&a[4]>r) mini = s, r = a[4];
    } while (next_permutation(p, p + 4));
    printf("%d", max(r * 2, 1));
    return 0;
}