답에 해당하는 점들을 포함하는 정사각형의 위치를 오른쪽 위로 최대한 옮겨보면 왼쪽 변과 아래쪽 변 위에 점이 존재한다.
임의의 두 점에 대해 각각 한쪽 성분을 가져와 새로운 점을 만들고 이 점이 왼쪽 아래 꼭지점이 되는 정사각형을 가정한다.
이러한 정사각형들 안 최대 별똥별 개수를 구한다.
시간복잡도는 $O(k^3)$
#include<cstdio> int n, m, l, k, r, x[100], y[100]; int main() { scanf("%d%d%d%d", &n, &m, &l, &k); for (int i = 0; i < k; i++) scanf("%d%d", x + i, y + i); for (int i = 0; i < k; i++) { for (int j = 0; j < k; j++) { int c = 0; for (int t = 0; t < k; t++) c += x[i] <= x[t] && x[t] <= x[i] + l&&y[j] <= y[t] && y[t] <= y[j] + l; if (r < c) r = c; } } printf("%d", k - r); return 0; }
안녕하세요
답글삭제저는 밑에 코드처럼 제출했는데 틀렸다고 나왔는데요
for (int n = 0;n < K;n++) {
for (int m = 0;m < K;m++) {
if (n == m) continue;
int cnt = 0;
int x = min(star[n][0], star[m][0]), y = min(star[n][1], star[m][1]);
for (int k = 0;k < K;k++) {
int dx = star[k][0] - x, dy = star[k][1] - y;
if (0 <= dx && dx <= L && 0 <= dy && dy <= L) cnt++;
}
ans = max(ans, cnt);
}
}
다른부분은 저는 두 좌표의 맨왼쪽 위를 정사각형의 왼쪽 위 귀퉁이라고 가정하고 풀었는데
혹시 어떤 부분이 논리에 어긋난지 알려주실 수 있나요?
으 코드 띄어쓰기가 안먹네요 ㅠㅠ
삭제왼쪽 위 귀퉁이에 점이 있는 경우 문제가 있네요.
삭제if (n == m) continue;
를 빼야할 것 같습니다.
크어 감사합니다 ㅠㅠ
삭제