문제 링크
문제
티어: 골드 3
알고리즘: 그리디, 이분 탐색
교실 게시판에 압정을 사용하여 만들어진 구멍들을 안보이게 하기 위해서 두 개의 같은 크기의 정사각형 모양의 종이로 가리려고 한다. 두 종이는 서로 떨어져도 되고 서로 겹치는 부분이 있어도 상관없지만 모든 구멍들을 포함해야 한다. 단, 각 구멍은 크기가 매우 작아, x, y 좌표로 표현되는 점으로 표현되고, 구멍이 종이의 경계나 모서리에 놓이는 것도 종이에 포함되는 것으로 한다. 게시판에 각 구멍의 위치가 주어지고, 두 종이가 모두 게시판의 틀에 대해서 수평과 수직으로 놓인다고 할 때, 모든 구멍을 가리는 가장 작은 정사각형 모양의 종이의 크기를 구하시오.
구멍의 위치를 표시하기 위해서 게시판의 왼쪽 아래 모서리를 기준으로 오른쪽으로 갈수록 x좌표가 커지고 위로 갈수록 y 좌표가 커지는 좌표계를 이용한다.
입력
첫째 줄에는 구멍의 개수인 n이 주어지고 (1 ≤ n ≤ 1000), 다음 n개의 줄에는 구멍의 위치로 x 좌표와 y 좌표가 주어진다. 입력으로 주어지는 좌표의 값은 절댓값이 30,000보다 작거나 같은 정수이다.
출력
첫째 줄에는 종이의 변의 길이를 출력하고 둘째 줄에는 한 종이의 왼쪽 아래 모서리의 위치를, 셋째 줄에는 다른 종이의 왼쪽 아래 모서리의 위치를 x좌표와 y좌표로 출력한다.
풀이
구해야 할 것은 모든 구멍을 가리는 가장 작은 정사각형 모양의 종이의 크기이다.
먼저, 좌표의 절댓값은 30,000보다 작거나 같은 정수이다. 이 말은 정사각형의 크기는 최대 30,000이라는 의미다.
그리고 정사각형은 크기가 클 수록 더 많은 점을 포함할 수 있고, 작을 수록 더 적은 점을 포함한다. 이러한 특징은 이분 탐색을 적용할 수 있음을 의미한다.
그러면 크기는 min = 1, max = 30,000에서 이분 탐색을 통해서 최적의 크기를 구하면 된다.
중요한 것은 크기를 정했을 때 그 크기로 점을 다 가릴 수 있는지 판단하는 것이다.
직접 좌표계에 점을 찍어보고 그 점들을 포함하는 최적의 정사각형을 그려보면, 이해가 쉬울 것이다.
좌표계에서 가장 아래에 있는 점을 주목하자, 그 점은 정사각형에 밑변에 포함되는 것이 최선의 선택이 된다. 왜냐하면 그 점 아래에는 어떤 점도 없기 때문이다. (공간의 낭비를 최소화)
가장 아래에 있는 점은 하나가 아닐 수 있다. 즉, x좌표가 다를 수 있는데 아무 점이나 선택해도 상관 없다. 어차피 모든 점을 가려하기 때문에 가장 아래에 있는 점이면 상관없다.
그리고 그 점을 밑변에 포함하는 모든 정사각형을 탐색해 보는 것이다. 이때 경우의 수는 30,000이다. 왜냐하면 정사각형의 최대 크기는 30,000이기 때문이다.
그리고 첫 번째 정사각형의 위치가 정해지면, 두 번째 정사각형의 위치도 정해진다.
왜냐하면 나머지 점은 두 번째 정사각형이 다 포함해야 하기 때문에 왼쪽 아래 모서리 좌표는 첫 번째 정사각형의 포함되지 않는 점 중에서 가장 아래에 있는 점의 y좌표와 가장 왼쪽에 있는 점의 x좌표가 된다.
마지막으로 모든 점이 정사각형에 포함되는지를 판단해서 min과 max를 조절하면 된다.
시간 복잡도는 O(30000 * log30000)이다.
소스 코드
import java.io.*;
import java.util.*;
class Coordinate {
int x, y;
Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int n, minSize;
static Coordinate fstCn;
static Coordinate secCn;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
Coordinate[] list = new Coordinate[n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
list[i] = new Coordinate(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
binarySearch(list);
System.out.println(minSize);
System.out.println(fstCn.x + " " + fstCn.y);
System.out.println(secCn.x + " " + secCn.y);
}
static void binarySearch(Coordinate[] list) {
int max = 30000;
int min = 1;
while (min <= max) {
int mid = (min + max) / 2;
if (isPosible(list, mid)) {
max = mid - 1;
} else {
min = mid + 1;
}
}
}
static boolean isPosible(Coordinate[] list, int size) {
Coordinate fDown = find(list, 1, new Coordinate(-30001, -30001), size); //아래이면서 가장 왼쪽에 있는 점
for(int i=0; i<=size; i++) {
Coordinate fCorner = new Coordinate(fDown.x - i, fDown.y);
Coordinate sLeft = find(list, 0, fCorner, size);
Coordinate sDown = find(list, 1, fCorner, size);
Coordinate sCorner = combine(sLeft, sDown);
if(check(fCorner, sCorner, size, list)) {
fstCn = fCorner;
secCn = sCorner;
minSize = size;
return true;
}
}
return false;
}
static boolean check(Coordinate fCorner, Coordinate sCorner, int size, Coordinate[] list) {
for (int i = 0; i < list.length; i++) {
if (!checkRange(list[i], fCorner, size) && !checkRange(list[i], sCorner, size)) {
return false;
}
}
return true;
}
static Coordinate combine(Coordinate left, Coordinate down) {
return new Coordinate(left.x, down.y);
}
static Coordinate find(Coordinate[] list, int dir, Coordinate cn, int size) {
Coordinate result = new Coordinate(30001, 30001);
if (dir == 0) {
//왼쪽이면서 가장 아래
for (int i = 0; i < list.length; i++) {
if (checkRange(list[i], cn, size)) {
continue;
}
if (result.x > list[i].x || (result.x == list[i].x && result.y > list[i].y)) {
result = list[i];
}
}
} else {
//아래이면서 가장 왼쪽
for (int i = 0; i < list.length; i++) {
if (checkRange(list[i], cn, size)) {
continue;
}
if (result.y > list[i].y || (result.y == list[i].y && result.x > list[i].x)) {
result = list[i];
}
}
}
if (result.x == 30001 && result.y == 30001) {
//이미 다 포함되어 있다면 겹친다.
return new Coordinate(cn.x, cn.y);
}
return result;
}
static boolean checkRange(Coordinate p, Coordinate cn, int size) {
if (((cn.x <= p.x) && (p.x <= cn.x + size)) && ((cn.y <= p.y) && (p.y <= cn.y + size))) {
return true;
}
return false;
}
}