1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef pair<int, int> PII; 4 const int N = 1010; //最多给了500个草的位置，所以最多有1000个数需要离散化 5 int C, n; 6 PII points[N]; //存储草的位置 7 int sum[N][N]; //前缀和数组 8 vector<int> numbers; //存储所有离散化之后的数 9 bool check(int len) { 10 for (int x1 = 1, x2 = 1; x2 < numbers.size(); x2++) { 11 while (numbers[x2] - numbers[x1] + 1 > len) { 12 x1++; 13 } 14 for (int y1 = 1, y2 = 1; y2 < numbers.size(); y2++) { 15 while (numbers[y2] - numbers[y1] + 1 > len) { 16 y1++; 17 } 18 if (sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] >= C) { 19 return true; 20 } 21 } 22 } 23 return false; 24 } 25 int get(int x) { 26 int l = 0, r = numbers.size() - 1; 27 while (l < r) { 28 int mid = (l + r) / 2; 29 if (numbers[mid] >= x) { 30 r = mid; 31 } else { 32 l = mid + 1; 33 } 34 } 35 return l; 36 } 37 int main() { 38 cin >> C >> n; 39 numbers.push_back(0); 40 for (int i = 0; i < n; i++) { 41 int x, y; 42 cin >> x >> y; 43 numbers.push_back(x); 44 numbers.push_back(y); 45 points[i] = {x, y}; 46 } 47 sort(numbers.begin(), numbers.end()); 48 numbers.erase(unique(numbers.begin(), numbers.end()), numbers.end()); 49 for (int i = 0; i < n; i++) { 50 int x = get(points[i].first), y = get(points[i].second); 51 sum[x][y]++; 52 } 53 for (int i = 1; i < numbers.size(); i++) { //计算前缀和 54 for (int j = 1; j < numbers.size(); j++) { 55 sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]; 56 } 57 } 58 int l = 1, r = 10000; //二分 59 while (l < r) { 60 int mid = (l + r) / 2; 61 if (check(mid)) { 62 r = mid; 63 } else { 64 l = mid + 1; 65 } 66 } 67 cout << l << endl; 68 return 0; 69 }