문제
2D 평면 위에 N개의 점이 주어진다. 이 점들을 모두 정사각형의 테두리(변 위) 위에 올릴 수 있는 가장 작은 정사각형의 한 변의 길이를 구한다. 단, 정사각형의 변은 좌표축에 평행해야 한다.
입력
첫째 줄에 점의 개수 N이 주어진다. 이후 N개의 줄에 각 점의 x, y 좌표가 주어진다.
출력
모든 점을 정사각형의 테두리 위에 올릴 수 있는 정사각형의 최소 한 변의 길이를 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 0 0 1 0 0 1 1 1 | 1 |
풀이
점들의 바운딩 박스를 기준으로 최소 정사각형 크기를 결정하고, 네 가지 배치를 검증하는 케이스워크 접근법을 사용한다.
- 모든 점의 x, y 좌표 최솟값/최댓값(x1, x2, y1, y2)을 구해 바운딩 박스를 계산한다.
- x 범위 또는 y 범위가 0이면(일직선 배치) 비영(non-zero) 범위를 변의 길이로 반환한다.
- 최소 정사각형의 크기 k =
max(x2-x1, y2-y1)로 설정한다. - k 크기의 정사각형을 네 가지 위치(좌하, 우하, 좌상, 우상)에 배치하고, 모든 점이 테두리 위에 있는지
check()함수로 검증한다. check()함수는 각 점이 정사각형의 네 변 중 하나 위에 있는지 확인한다.
핵심 아이디어: 최소 정사각형 크기는 바운딩 박스의 긴 변 길이로 고정되며, 짧은 변에 여유 공간을 활용해 정사각형을 슬라이드하는 방식으로 네 가지 극단 배치만 확인하면 충분하다.
코드
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> x, y;
inline bool check(int lx, int rx, int by, int ty)
{
for (int i = 0; i < n; i++)
{
if ((x[i] == lx || x[i] == rx) && by <= y[i] && y[i] <= ty)
continue;
if ((y[i] == by || y[i] == ty) && lx <= x[i] && x[i] <= rx)
continue;
return false;
}
return true;
}
int solve(void)
{
cin >> n;
x.resize(n);
y.resize(n);
for (int i = 0; i < n; i++)
cin >> x[i] >> y[i];
int x1 = x[0], x2 = x[0], y1 = y[0], y2 = y[0];
for (int i = 1; i < n; i++)
{
x1 = min(x1, x[i]);
x2 = max(x2, x[i]);
y1 = min(y1, y[i]);
y2 = max(y2, y[i]);
}
if (x2 - x1 == 0 || y2 - y1 == 0)
return max(x2 - x1, y2 - y1);
int k = max(x2 - x1, y2 - y1);
if (check(x1, x1 + k, y1, y1 + k))
return k;
if (check(x2 - k, x2, y1, y1 + k))
return k;
if (check(x1, x1 + k, y2 - k, y2))
return k;
if (check(x2 - k, x2, y2 - k, y2))
return k;
return -1;
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << solve();
return 0;
}복잡도
- 시간: O(N) — 바운딩 박스 계산 O(N) + 4회의
check()각 O(N) - 공간: O(N) — 점 좌표 저장