알고리즘

  • 한 점에서 x축으로의 범위를 정하고, 다른 점에서 y축으로의 범위를 정하는 방식으로 모든 두개의 점 조합으로 트래펄린을 설치한다.

코드

#include <iostream>
 
using namespace std;
 
int n, m, l, k;
pair<int, int> s[110];
 
int max(int a, int b) {
	return a < b ? b : a;
}
 
 
int main() {
	cin >> n >> m >> l >> k;
 
	int a, b;
	for (int i = 0; i < k; i++) {
		cin >> a >> b;
		s[i] = { a, b };
	}
 
	int cnt = 0;
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < k; j++) {
			int temp = 0;
			for (int e = 0; e < k; e++) {
				if (s[i].first <= s[e].first && s[i].first + l >= s[e].first
					&& s[j].second <= s[e].second && s[j].second + l >= s[e].second)
					temp++;
			}
			cnt = max(cnt, temp);
		}
	}
	cout << k - cnt;
}