| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 13421 |
| 문제명 | 국민 랜드 |
| 레벨 | 골드 2 |
| 분류 |
유니모달 함수의 최솟값 |
| 시간복잡도 | O(1) |
| 사용한 언어 | Python 3.11 |
| 제출기록 | 31120KB / 36ms |
| 최고기록 | 36ms |
| 해결날짜 | 2024/10/28 |
"""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()