글 읽기 - 어디가 틀렸는지 모르겠습니다.

kth990303 3년 전 0

비스듬하게 트램펄린 배치는 불가능하므로,

어떤 별을 꼭짓점으로 잡아 그 별을 기준으로

1사분면, 2사분면, 3사분면, 4사분면에 해당되는 각각의 L*L 크기의 정사각형(트램펄린)에 별이 있으면 각각의 cnt를 증가시키고,

가장 큰 cnt가 답이되도록 했습니다.

온갖 반례를 집어넣어도 맞는 듯 하네요. 딱히 틀린 이유를 모르겠습니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 500001;
int N, M, L, K, ans;
vector<pair<int, int>> v;
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M >> L >> K;
	v.resize(K);
	for (int i = 0; i < K; i++) {
		cin >> v[i].first >> v[i].second;
	}
	for (int i = 0; i < K; i++) {
        // i번째 별에 대해 각각 1,2,3,4사분면
		int cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0;
        // 어차피 자기 자신이면 if문에 포함되므로 무조건 트램펄린에 1개 이상 담긴다
		for (int j = 0; j < K; j++) {
			int x1 = v[i].first;
			int y1 = v[i].second;
			int x2 = v[j].first;
			int y2 = v[j].second;
            // i번째 별에 대해 L*L 트램펄린 1사분면
			if (x2 - x1 >= 0 && y2 - y1 >= 0 && x2 - x1 <= L && y2 - y1 <= L)
				cnt1++;
            // i번째 별에 대해 L*L 트램펄린 2사분면
			if (x1 - x2 >= 0 && y2 - y1 >= 0 && x1 - x2 <= L && y2 - y1 <= L)
				cnt2++;
            // i번째 별에 대해 L*L 트램펄린 3사분면
			if (x1 - x2 >= 0 && y1 - y2 >= 0 && x1 - x2 <= L && y1 - y2 <= L)
				cnt3++;
            // i번째 별에 대해 L*L 트램펄린 4사분면
			if (x2 - x1 >= 0 && y1 - y2 >= 0 && x2 - x1 <= L && y1 - y2 <= L)
				cnt4++;
		}
        // 트램펄린에 가장 많이 담을 수 있을 때가 ans
		ans = max({ans, cnt1, cnt2, cnt3, cnt4});
	}
    // 지구로 떨어지는 별똥별 개수
	cout << K - ans << "\n";
}

kth990303 3년 전 5

* *

이런 경우 각 꼭짓점에 트램펄린 설치하면 안되겠네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 틀렸는지 모르겠습니다.

kth990303 3년 전 0

kth990303 3년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말