풀이
(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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이