• 문제 설명에 좀 명확하지 않은 부분들이 있다. 이는 뒤에 언급.
• 조건을 만족하는 새로운 좌표는 (d,d), (d,-d), (-d,d), (-d,-d) 이다. 각 점은 d에 바뀌면 따라 직선을 따라 움직인다. 고정된 점들과 직선으로 움직이는 점들과의 거리는 맨하튼 거리를 쓰든 유클리드 거리를 쓰든 유니모달한 함수가 되는 것은 쉽게 알수 있다. 따라서 삼분탐색을 통해서 함수의 최솟값과 그때의 d값을 쉽게 구할 수 있다.
• 조금 귀찮은 부분은, 각각의 기존 좌표들을 어떤 새좌표와 매칭시킬 것인가이다. 가장 비용이 최소가 되는 매칭을 구하는 효율적인 방법이 있을지도 모르지만, 그냥 모든 가짓수를 다 고려해도 4! = 24가지 뿐이므로 그냥 브루트포스로 24가지 매칭에 대해서 비용을 모두 구하고 최솟값을 취해도 된다.
• 자.. 이렇게 구상해놓고 구현해서 제출했다가, 10번 이상의 WA를 받았다.. 그리고 계속 WA를 받는 과정에서, 구현과 풀이를 디버깅을 하면서 풀이상 실수한 점을 몇 개 발견했는데, 놀랍게도 이는 별 영향을 미치지 않았다. (결국 원인은 코딩상의 실수였다)
• 먼저, 처음에는 d가 자연수라고 단순하게 생각하고, d에 대해서 정수범위의 삼분탐색을 시도했다. 그러나 뒤늦게 한변의 길이가 정수여야 한다는 문장을 재확인했고, d가 0.5단위가 되도록 수정했다. 하지만 이것은 오답의 원인이 아니었고, 그냥 정수단위로만 탐색해도 정답을 항상 구할수 있다는 것을 풀이를 정리하는 과정에서 깨달았다.
• 다음 발견한 실수는, f(d)의 값을 모든 매칭 방법에 대한 비용의 최솟값으로 정한 것이었다. 한 변과 원점과의 거리가 d이고, 새로운 좌표 4개가 각각 어떤 원래좌표와 대응될지가 정해져 있을 때의 비용은 당연히 유니모달이다. 하지만, 모든 매칭방법에 대한 최솟값, 즉 유니모달 함수들의 최솟값으로 만들어지는 함수는 유니모달이 아니다. 그래서 바로 삼분탐색을 쓸수 없다. 올바른 방법은, 각 매칭방법에 대해서 각각 삼분탐색을 돌려서 최솟값을 찾은 뒤에, 그중에서 최솟값을 다시 찾는 것이다. 삼분탐색을 4!번 돌려야 제대로 된 답을 찾을수 있다.. 고 생각했는데, 나중에 다른 사람들의 코드를 보니 그냥 f(d)를 유니모달 함수들의 최솟값으로 정의해놓고, 한번의 삼분탐색으로 돌렸는데도 잘만 AC를 받았다. 왜 이게 되는지.. 이 함수만의 특성이 있는지, 데이터가 약한건지, 아니면 또다른 이유가 있는건지는 확인 불가.
• 또 다른 실수는, d=0이 되는 경우를 처리하는 것이다. 예를 들어, 원래 좌표가 (0,0),(0,1),(1,0),(0,-1)일 때에는 d=0일때 최솟값을 갖게 되는데, 이는 정사각형이라는 조건을 만족하지 못한다. 이 경우는 답을 1로 (d=0.5) 출력해야 한다
  • 나중에 알게된 것은 이것을 빼먹으면 99%에서 틀리게 된다는 것이었다. 이 경우를 생각않고, d를 정수단위로만 체크하면 여기에서 오답을 받게 된다.
• 이렇게 세가지 실수를 발견해서 고쳤는데도 계속 WA를 반복하는 바람에 좀더 식을 정리해서 보기로 했다;
• 매칭을 고정된 경우의 식을 다시 적어보자. (x1,y1),(x2,y2),(x3,y3),(x4,y4)가 각각 (d,d),(d,-d),(-d,d),(-d,-d) 로 이동할때의 비용을 분리해보면, 어떤 좌표가 d로 이용하는 비용은 |x1-d|, |y1-d|, … 이런식이고, 어떤 좌표가 -d로 이동하는 비용은 |x4-(-d)|, |y4-(-d)|, .. 이런 식이다. 바꿔쓰면 |d-x1| 또는 |d -(-x4)| 형태라서 결국 절댓값 1차 함수의 합 형태이다. f(d) = sigma(|d-a_i|) 꼴일 경우에는, d가 a_i들의 중앙값일때 최솟값을 갖는다는 것이 잘 알려져있으므로, 결국 저 8개의 값중에서 5번째로 큰 값을 찾으면 된다 (4번째와 5번째가 둘다 중앙값에 해당하지만, 비용이 같으면 큰 변을 취하라는 조건이 있으므로 5번째를 택한다). 앞의 매칭에서는 x1,y1,x2,-y2,-x3,y3,-x4,-y4 중에서 5번째 값을 찾으면 된다. 매칭이 달라지면, x_i와 y_i 앞에 붙는 부호들만 바꿔주는 방식으로 찾으면 된다.
  • d가 0.5의 배수가 되는 경우를 무시해도 되는 이유는 이것이다. d는 원래 있던 어떤 좌표의 x값이나 y값을 갖게 되므로 항상 정수가 된다.
• 이렇게 하면 삼분탐색 없이도, 원소 8개짜리 리스트의 중앙값을 찾는 작업을 4!번 해주는 것만으로 답을 찾을 수 있다. 원소 갯수가 고정이므로, 중앙값 찾는것이나 4! 반복하는거나 모두 O(1)이다 보니, 결국 전체 시간복잡도는 O(1)이다.
• 코딩실수로 삼분탐색에서 WA를 많이 받긴 했지만, 삼분탐색으로 푸는것도 당연히 가능하다. 이 경우에는 탐색범위를 0에서 원래 좌표의 x값이나 y값들중 최댓값으로 잡고 돌리게 되므로, 시간복잡도가 O(logX)가 된다. (X는 좌표값의 절댓값의 최댓값)

"""Solution code for "BOJ 13421. 국민 랜드".

- Problem link: https://www.acmicpc.net/problem/13421
- Solution link: http://www.teferi.net/ps/problems/boj/13421
"""

import itertools

SIGNS = ((1, 1), (1, -1), (-1, 1), (-1, -1))
INF = float('inf')


def main():
    poses = [[int(x) for x in input().split()] for _ in range(4)]

    min_cost_and_d = (INF, None)
    for signs_perm in itertools.permutations(SIGNS):
        m = []
        for (sign_x, sign_y), (px, py) in zip(signs_perm, poses):
            m.append(sign_x * px)
            m.append(sign_y * py)
        argmin = sorted(m)[4]
        cost = sum(abs(argmin - m_i) for m_i in m)
        min_cost_and_d = min(min_cost_and_d, (cost, -argmin))
    answer = min_cost_and_d[1] * -2

    print(1 if answer == 0 else answer)


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 13421. 국민 랜드".

- Problem link: https://www.acmicpc.net/problem/13421
- Solution link: http://www.teferi.net/ps/problems/boj/13421
"""

import itertools
import functools
from teflib import ternsearch

INF = float('inf')


def compute_cost(d, old_poses):
    new_poses = [(d, d), (d, -d), (-d, d), (-d, -d)]
    return sum(
        abs(old_x - new_x) + abs(old_y - new_y)
        for (old_x, old_y), (new_x, new_y) in zip(old_poses, new_poses)
    )


def main():
    old_poses = [[int(x) for x in input().split()] for _ in range(4)]

    min_cost_and_d = (INF, None)
    for old_poses_perm in itertools.permutations(old_poses):
        cost_and_d = ternsearch.min_of_unimodal_func(
            -max(max(abs(x), abs(y)) for x, y in old_poses),
            1,
            functools.partial(compute_cost, old_poses=old_poses_perm),
            also_return_argmin=True,
        )
        min_cost_and_d = min(min_cost_and_d, cost_and_d)
    answer = min_cost_and_d[1] * -2

    print(1 if answer == 0 else answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.ternsearch.min_of_unimodal_func