알고리즘
- 한 점에서 x축으로의 범위를 정하고, 다른 점에서 y축으로의 범위를 정하는 방식으로 모든 두개의 점 조합으로 트래펄린을 설치한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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;
}