코드 복사/붙여넣기 하는 당신이 아름답습니다.

2496: 금강석

풀이

(x, y)의 좌표계를 변환하자.

(x, y) => (x+y, x-y)로 좌표를 변환시키면 좌표계가 45도 기울어지고, 점 사이의 간격이 root(2)배만큼 늘어난다.

좌표계를 돌리고 나면 마름모가 정사각형이 되므로, 문제를 풀기 한결 수월해진다.

T가 100밖에 안 된다는 점을 주목하자.

정답에 포함되는 어떤 금강석들의 집합이 있다고 하자.

이 금강석들을 포함하는 사각형은, 얘네들을 모두 포함하는 선에서 이리저리 잘 옮길 수 있을 것이다.

정답을 벗어나지 않는 선에서, 사각형을 최대한 오른쪽 아래로 땡겨보자.

항상 두 개의 금강석이 왼쪽과 위쪽 변에 걸치게 만들 수 있다.

이를 이용해 두 개 이하의 금강석을 골라 사각형의 시작 모서리를 잡는 데 O(T^2), 각 금강석들이 이 사각형에 포함되는지 검사하는 데 O(T), 총 O(T^3)에 문제를 해결할 수 있다.

다만 마름모가 반드시 정수 좌표에 놓여야 한다는 조건이 있으므로 이를 주의해서 구현하자.

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, t, k;
int dap, dap_x, dap_y;
struct abc {
    int x, y;
} a[111];

void go(int x, int y) {
    int cnt = 0;
    for (int i = 1; i <= t; i++) {
        if (x <= a[i].x && a[i].x <= x+k &&
            y <= a[i].y && a[i].y <= y+k) cnt++;
    }
    if (cnt > dap) {
        dap_x = (x+y)/2;
        dap_y = (x-y)/2;
        dap = cnt;
    }
}

int main() {
    cin >> n >> m >> t >> k;
    for (int i = 1; i <= t; i++) {
        int x, y;
        cin >> x >> y;
        a[i].x = x+y, a[i].y = x-y;
    }

    dap = dap_x = dap_y = -1;
    for (int i = 1; i <= t; i++) {
        for (int j = 1; j <= t; j++) {
            int x = a[i].x, y = a[j].y;
            if ((x+y)%2) go(x+1, y), go(x-1, y), go(x, y+1), go(x, y-1);
            else go(x, y);
        }
    }

    cout << dap_x+k/2 << " " << dap_y << "\n" << dap;

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2020-03-08 15:58

Read more posts by this author