[BOJ] 2403: 게시판 구멍 가리기

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

BOJ - 게시판 구멍 가리기

문제 유형: 기하학, 수학, 이진 탐색

문제 난이도: Gold III

시간 제한: 2초

메모리 제한: 128MB

 

문제

교실 게시판에 압정을 사용하여 만들어진 구멍들을 안보이게 하기 위해서 두 개의 같은 크기의 정사각형 모양의 종이로 가리려고 한다. 두 종이는 서로 떨어져도 되고 서로 겹치는 부분이 있어도 상관없지만 모든 구멍들을 포함해야 한다. 단, 각 구멍은 크기가 매우 작아,  x, y 좌표로 표현되는 점으로 표현되고, 구멍이 종이의 경계나 모서리에 놓이는 것도 종이에 포함되는 것으로 한다.  게시판에 각 구멍의 위치가 주어지고, 두 종이가  모두 게시판의 틀에 대해서 수평과 수직으로 놓인다고 할 때,  모든 구멍을 가리는 가장 작은 정사각형 모양의 종이의 크기를 구하시오.

구멍의 위치를 표시하기 위해서 게시판의 왼쪽 아래 모서리를 기준으로 오른쪽으로 갈수록 x좌표가 커지고 위로 갈수록 y 좌표가 커지는 좌표계를 이용한다. 

 

입력

첫째 줄에는 구멍의 개수인 n이 주어지고 (1 ≤ n ≤ 1000), 다음 n개의 줄에는 구멍의 위치로 x 좌표와 y 좌표가 주어진다. 입력으로 주어지는 좌표의 값은 절댓값이 30,000보다 작거나 같은 정수이다.

 

출력

첫째 줄에는 종이의 변의 길이를 출력하고 둘째 줄에는 한 종이의 왼쪽 아래 모서리의 위치를, 셋째 줄에는 다른 종이의 왼쪽 아래 모서리의 위치를 x좌표와 y좌표로 출력한다.

 

풀이

이 문제는 가능한 최소의 길이를 가지는 모서리를 구해야 하는데,

정사각형의 길이가 가능한 범위는 0 ~ 60000이다. (양쪽 30000)

이진 탐색을 통해서 가능한 길의의 하한선을 구하는 게 핵심이다.

아래의 체킹 방식으로 가능하다면 right을 mid-1로, 불가능하다면 left를 mid+1로 한다.

가능하면 중위값보다 더 짧은 길이로 시도하고, 불가능하면 더 긴 길이로 시도하라는 의미이다.

 

이진탐색으로 길이를 구하면서, 그 길이의 정사각형 2개로 모든 점을 가릴 수 있는지 알아봐야 하는데,

첫 번째 사각형을 놓는 방법으로는, 모든 구멍에다가 그 구멍이 정사각형의 좌측상단, 좌측하단, 우측상단, 우측하단 꼭짓점인 경우를 가정하는 방법으로 했다.

각각의 경우로 범위를 잡아주고, 다른 구멍들에 대해서 범위에 속하지 않는 구멍들은 따로 배열에 담아둔다.

그 구멍들은 이제 두 번째 사각형으로 덮어야 한다.

이제 하나의 정사각형으로 나머지 모든 구멍을 덮어야 한다.

즉, 나머지 모든 구멍들의 가장 왼쪽값, 가장 아래 값을 잡아서 그 부분에 대해서 두 번째 사각형의 범위를 잡는다.

남은 구멍들이 그 두 번째 사각형의 범위에 소속되는지 조사한다.

모두 포함된다면, 두 정사각형으로 막을 수 있는 것이다.

 

 

코드

C++

#include <bits/stdc++.h>
#define LIMIT 30000

using namespace std;
typedef pair<int, int> pii;

int n;
vector<pii> points;
bool check(int len, pii &p1, pii &p2) {
  for (auto &base : points) {
    vector<pii> first_square_positions = {
        {base.first, base.second},
        {base.first - len, base.second},
        {base.first, base.second - len},
        {base.first - len, base.second - len}};

    for (auto &pos1 : first_square_positions) {
      int x1 = pos1.first;
      int y1 = pos1.second;
      int right1 = x1 + len;
      int top1 = y1 + len;
      vector<pii> outBounds;
      int newMinX = LIMIT, newMinY = LIMIT;
      for (auto &p : points) {
        if (!(p.first >= x1 && p.first <= right1 && p.second >= y1 &&
              p.second <= top1)) {
          outBounds.emplace_back(p);
          newMinX = min(newMinX, p.first);
          newMinY = min(newMinY, p.second);
        }
      }
      if (outBounds.empty()) {
        p1 = {x1, y1};
        p2 = {x1, y1};
        return true;
      }
      int x2 = newMinX;
      int y2 = newMinY;
      int right2 = x2 + len;
      int top2 = y2 + len;

      bool all_covered = true;
      for (auto &p : outBounds) {
        if (!(p.first >= x2 && p.first <= right2 && p.second >= y2 &&
              p.second <= top2)) {
          all_covered = false;
          break;
        }
      }

      if (all_covered) {
        p1 = {x1, y1};
        p2 = {x2, y2};
        return true;
      }
    }
  }
  return false;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  cin >> n;
  points.resize(n);
  int x, y;
  for (int i = 0; i < n; ++i) {
    cin >> x >> y;
    points[i] = {x, y};
  }
  int left = 0;
  int right = 2 * LIMIT;
  int result_len = right;
  pii result_p1, result_p2;

  while (left <= right) {
    int mid = left + (right - left) / 2;
    pii temp_p1, temp_p2;
    if (check(mid, temp_p1, temp_p2)) {
      result_len = mid;
      result_p1 = temp_p1;
      result_p2 = temp_p2;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  cout << result_len << "\n";
  cout << result_p1.first << " " << result_p1.second << "\n";
  cout << result_p2.first << " " << result_p2.second << "\n";

  return 0;
}