2337.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2337 on 2006-08-25 at 17:06:52 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1024;
const int NN = 4 * N;

class Tree {
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 disperse(int*, int*);
int maxGet(int, int);
void insert(int, int, int, int, int);

Event e[2*N];
Tree m[N];
int x[2*N], n;
int tmax[NN], lmax[NN], rmax[NN], sum[NN];

int main()
{
	int T;

	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		int a; scanf("%d %d", &n, &a);
		for(int i = 0; i < n; i++) m[i].make();
		if(n < 2) { printf("%d\n", n); continue; }
		int xl = N, xh = -1, yl = N, yh = -1;
		for(int i = 0; i < n; i++) {
			xl <?= m[i].x; xh >?= m[i].x;
			yl <?= m[i].y; yh >?= m[i].y;
		}
		int best = 0, ph = -1, tw = max(xh-xl, 1), th = max(yh-yl, 1);
		a <?= tw*th;
		if(a == tw*th) best = n;
		for(int w = tw; w > 0; w--) {
			if(best == n) break;
			int h = a/w;
			if(h > th || h == ph) continue;
			ph = h;
			best >?= maxGet(w, h);
		}
		printf("%d\n", best);
	}

	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]);
}