poj 3179

题意
在一个二维平面上,有N颗草,每颗草的大小是1∗1,左下角坐标为xi,yi.要求一个正方形,正方形的边平行于x或y轴,正方形里面包含至少C颗草.求正方形的最小边长.注意,同一个区域可能生长多颗草.

思维很简单，前缀+二分+离散化，但是实现起来细节满满

懒得解释了，直接上代码。

#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <stack>

#define INF 0x3f3f3f3f
#define IMAX 2147483646
#define LINF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define uint unsigned int

using namespace std;

int c, n,len;
int a[555], b[555],disc[1111],s[1111][1111];//s[555][555]

bool check(int x) {
	int pos = lower_bound(disc + 1, disc + len + 1, x) - disc - 1,tx,ty;
	//int pos = lower_bound(disc + 1, disc + n*2 + 1, x) - disc - 1,tx,ty;
	for (int i = pos; i <= len; i++) 
		for (int j = pos; j <= len; j++) {
			tx = upper_bound(disc + 1, disc + len + 1, disc[i] - x) - disc;
			//tx = upper_bound(disc + 1, disc + n*2 + 1, disc[i] - x) - disc;
			ty = upper_bound(disc + 1, disc + len + 1, disc[j] - x) - disc;
			//if (s[i][j] - s[i - tx - 1][j] - s[i][j - ty - 1] + s[i - tx - 1][j - ty - 1] >= c)
			if (s[i][j] - s[tx - 1][j] - s[i][ty - 1] + s[tx - 1][ty - 1] >= c)
				return true;
		}

	return false;
}

int main() {
	scanf("%d%d", &c, &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", a + i, b + i);
		disc[i * 2 - 1] = a[i];//disc[i * 2] = a[i]
		disc[i * 2] = b[i];//disc[i * 2 + 1]
	}
	sort(disc + 1, disc + n * 2 + 1);
	len = unique(disc + 1, disc + n * 2 + 1) - disc - 1;
	for (int i = 1,x,y; i <= n; i++) {
		x = lower_bound(disc + 1, disc + len + 1, a[i]) - disc;
		y = lower_bound(disc + 1, disc + len + 1, b[i]) - disc;
		/*x = lower_bound(disc + 1, disc + n * 2 + 1, a[i]) - disc;
		y = lower_bound(disc + 1, disc + n * 2 + 1, b[i]) - disc;*/
		s[x][y]++;
	}
	for (int i = 1; i <= len; i++) 
		for (int j = 1; j <= len; j++) 
			s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
	int l = 1,r = disc[len],mid;
	while (l <= r) {
		mid = (l + r) / 2;
		if (check(mid))r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n", l);

	return 0;
}