2369.cpp

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

/* This Code is Submitted by wywcgs for Problem 2369 on 2006-10-06 at 11:07:20 */
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N = 256;
 
class Rect {
public:
	int x1, y1, x2, y2;
	Rect() {}
	Rect(int cx1, int cy1, int cx2, int cy2) : x1(cx1), y1(cy1), x2(cx2), y2(cy2) {}
	bool overlap(const Rect&) const;
};
bool Rect::overlap(const Rect& r) const {
	if(x2 <= r.x1 || r.x2 <= x1 || y2 <= r.y1 || r.y2 <= y1) return false;
	else return true;
}
 
class Point {
public:
	int x, y;
	Rect d, u;
	void make() { scanf("%d %d", &x, &y); }
	void city(int);
};
void Point::city(int p) {
	d = Rect(2*x-p, 2*(y-p), 2*x+p, 2*y);
	u = Rect(2*x-p, 2*y, 2*x+p, 2*(y+p));
}
 
class Graph {
private:
	vector<int> g[N];
	int n, m, h[N], id[N];
	int cnt, scnt, dfn[N], low[N], cur[N];
	int stack[N], top, est[N], etop;
	Point p[N>>1];
	bool goodLabel(int);
	void dfs(int);
public:
	void make();
	int maxRect();
};
void Graph::make() {
	scanf("%d", &n); m = n*2;
	for(int i = 0; i < n; i++) p[i].make();
}
int Graph::maxRect() {
	int ht = 40000, lt = 0;
	while(ht != lt) {
		int mid = (lt+ht+1)/2;
		if(goodLabel(mid)) lt = mid;
		else ht = mid-1;
	}
	return ht;
}
bool Graph::goodLabel(int s) {
	for(int i = 0; i < n; i++) p[i].city(s);
	for(int i = 0; i < m; i++) g[i].clear();
	for(int i = 0; i < n; i++)
		for(int j = i+1; j < n; j++) {
			if(p[i].d.overlap(p[j].d)) { g[i].push_back(j+n); g[j].push_back(i+n); }
			if(p[i].u.overlap(p[j].d)) { g[i+n].push_back(j+n); g[j].push_back(i); }
			if(p[i].d.overlap(p[j].u)) { g[i].push_back(j); g[j+n].push_back(i+n); }
			if(p[i].u.overlap(p[j].u)) { g[i+n].push_back(j); g[j+n].push_back(i); }
		}
	memset(dfn, -1, sizeof(dfn));
	cnt = scnt = 0;
	for(int i = 0; i < m; i++) cur[i] = g[i].size()-1;
	for(int i = 0; i < m; i++)
		if(dfn[i] == -1) dfs(i);
	for(int i = 0; i < n; i++)
		if(id[i] == id[i+n]) return false;
	return true;
}
void Graph::dfs(int src) {
	etop = top = 0;
	stack[top++] = src;
	while(top != 0) {
		int	c = stack[top-1];
		if(dfn[c] == -1) { h[c] = dfn[c] = low[c] = cnt++; est[etop++] = c; }
		for(; cur[c] >= 0; cur[c]--) {
			int no = g[c][cur[c]];
			if(dfn[no] == -1) { stack[top++] = no; break; }
			h[c] <?= low[no];
		}
		if(cur[c] >= 0) continue;
		top--; int k;
		if(h[c] != low[c]) { low[c] = h[c]; continue; }
		do {
			k = est[--etop];
			id[k] = scnt; low[k] = N;
		} while(k != c);
		scnt++;
	}
}
 
Graph g;

int main()
{
	int T;
	
	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		g.make();
		printf("%d\n", g.maxRect());
	}
	
	return 0;
}