2362.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2362 on 2006-09-14 at 15:51:34 */ 
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int N = 512;
const int NN = 4*N;
 
class Field {
public:
	int x, y;
	void make() { scanf("%d %d", &x, &y); }
};
 
class Event {
public:
	int y, o;
	bool ent;
	void set(int cy, int co, bool e) { y = cy; o = co; ent = e; }
	bool operator <(const Event& e) const { return y < e.y; }
};
 
int sum[NN], lmax[NN], rmax[NN], tmax[NN];
Field m[N];
Event e[2*N];
int x[2*N], n;
 
int disperse(int*, int*);
int maxGet(int, int);
void insert(int, int, int, int, int);
 
int main()
{
	int c;
	while(scanf("%d %d", &c, &n) != EOF) {
		for(int i = 0; i < n; i++) m[i].make();
		int l = 0, h = 10000;
		while(l != h) {
			int mid = (l+h)/2;
			int cn = maxGet(mid, mid);
			if(cn >= c) h = mid;
			else l = mid+1;
		}
		printf("%d\n", h+1);
	}
	
	return 0;
}
 
int disperse(int* b, int* e)
{
	int n = e-b, dn = 1;
	sort(b, e);
	for(int i = 1; i < n; i++)
		if(b[i] != b[i-1]) b[dn++] = b[i];
	return dn;
}
int maxGet(int w, int h)
{
	for(int i = 0; i < n; i++) {
		e[2*i].set(m[i].y, i, true); e[2*i+1].set(m[i].y+h+1, i, false);
		x[2*i] = m[i].x; x[2*i+1] = m[i].x+w+1;
	}
	int en = n << 1, j;
	int xn = disperse(x, x+en), best = 0;
	sort(e, e+en);
	memset(sum, 0, sizeof(int)*2*xn);
	for(int i = 0; i < en; i = j) {
		for(j = i; j < en && e[i].y == e[j].y; j++) {
			int o = e[j].o, x1 = lower_bound(x, x+xn, m[o].x)-x,
				x2 = lower_bound(x, x+xn, m[o].x+w+1)-x;
			if(e[j].ent) { insert(0, x1, 1, 0, xn); insert(0, x2, -1, 0, xn); }
			else { insert(0, x1, -1, 0, xn); insert(0, x2, 1, 0, xn); }
		}
		best >?= tmax[0];
	}
	return best;
}
void insert(int o, int px, int v, int x, int y)
{
	int l = 2*o+1, r = 2*o+2;
	if(y-x == 1) { sum[o] += v; lmax[o] = rmax[o] = tmax[o] = sum[o]; return; }
	if(px < (y+x)/2) insert(l, px, v, x, (y+x)/2);
	else insert(r, px, v, (y+x)/2, y);
	sum[o] += v;
	tmax[o] = max(rmax[l]+lmax[r], max(tmax[l], tmax[r]));
	lmax[o] = max(lmax[l], sum[l]+lmax[r]);
	rmax[o] = max(rmax[r], rmax[l]+sum[r]);
}