2048.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2048 on 2006-02-16 at 05:28:56 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 512;
const int INF = 1 << 30;

class Edge {
public:
	int x, y1, y2;
	bool enter;
	void set(int, int, int, bool);
	bool operator <(const Edge&) const;
};
void Edge::set(int cx, int cy1, int cy2, bool e) {
	x = cx; y1 = cy1; y2 = cy2; enter = e;
}
bool Edge::operator <(const Edge& e) const {
	if(x != e.x) return x > e.x;
	else if(y1 != e.y1) return y1 < e.y1;
	else return y2 > e.y2;
}

int xc[MAX], yc[MAX], xn, yn, bx, by;

int compress(int*, int*, int);
void update(int, int);

int main()
{
	int i, j, t, T;
	int n, w, h, iw, ih, x[MAX], y[MAX];
	int over[MAX], l[MAX], d[MAX];
	Edge edge[MAX];

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d %d", &n, &w, &h);
		int m = 2 * n;
		for(i = 0; i < m; i++) scanf("%d %d", &x[i], &y[i]);
		scanf("%d %d", &iw, &ih);
		x[m] = y[m] = 0; x[m+1] = w; y[m+1] = h; m += 2; n++;
		xn = compress(x, xc, m); yn = compress(y, yc, m);
		for(i = 0; i < n; i++) {
			edge[2*i].set(x[2*i], y[2*i], y[2*i+1], false);
			edge[2*i+1].set(x[2*i+1], y[2*i], y[2*i+1], true);
		}
		sort(edge, edge+m); bx = by = INF;
		memset(over, 0, sizeof(over)); memset(l, 0, sizeof(l)); d[yn-1] = 0;
		for(i = 1; i <= m; i++) {
			for(j = yn-2; j >= 0; j--) {
				if(over[j] > 0) l[j] = 0;
				else l[j] += xc[edge[i-1].x]-xc[edge[i].x];
				if(l[j] < iw) d[j] = 0;
				else d[j] = d[j+1] + yc[j+1] - yc[j];
				if(d[j] >= ih) update(xc[edge[i].x], yc[j]);
			}
			for(j = edge[i].y1; j < edge[i].y2; j++) edge[i].enter ? over[j]++ : over[j]--;
		}
		if(bx == INF) printf("Fail!\n");
		else printf("%d %d\n", bx, by);
	}
	
	return 0;
}

int compress(int* src, int* dis, int n)
{
	int i, dn;
	for(i = 0; i < n; i++) dis[i] = src[i];
	sort(dis, dis+n);
	for(dn = i = 0; i < n; i++)
		if(i == 0 || dis[i] != dis[i-1]) dis[dn++] = dis[i];
	for(i = 0; i < n; i++)
		src[i] = find(dis, dis+dn, src[i]) - dis;
	return dn;
}
void update(int x, int y)
{
	bool better;
	if(by != y) better = (y < by);
	else better = (x < bx);
	if(better) bx = x, by = y;
}