1119.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1119 on 2006-01-12 at 01:20:48 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 256;
const double eps = 1e-3;

class Map {
public:
	double x1, y1, x2, y2;
	void set(double, double, double, double);
};
void Map::set(double a, double b, double c, double d) {
	x1 = a; y1 = b; x2 = c; y2 = d;
}

int find(double*, int, int, double);
inline int fcmp(double, double);

int main()
{
	Map map[MAX];
	bool ex[MAX][MAX];
	double x[MAX], y[MAX], xa, xb, ya, yb;
	int n, t, i, j, k;
	
	for(t = 1; scanf("%d", &n) != EOF && n != 0; t++) {
		memset(ex, false, sizeof(ex));
		for(i = 0; i < n; i++) {
			scanf("%lf %lf %lf %lf", &xa, &ya, &xb, &yb);
			x[2*i] = xa, x[2*i+1] = xb;
			y[2*i] = ya, y[2*i+1] = yb;
			map[i].set(xa, ya, xb, yb);
		}
		int m = 2 * n;
		sort(x, x+m); sort(y, y+m);
		double area = 0;
		for(i = 0; i < n; i++) {
			int u = find(y, 0, m-1, map[i].y2), d = find(y, 0, m-1, map[i].y1);
			int r = find(x, 0, m-1, map[i].x2), l = find(x, 0, m-1, map[i].x1);
			for(j = l; j < r; j++)
				for(k = d; k < u; k++)
					if(!ex[j][k]) ex[j][k] = true, area += (x[j+1]-x[j])*(y[k+1]-y[k]);
		}
		printf("Test case #%d\n", t);
		printf("Total explored area: %.2lf\n\n", area);
	}
	
	
	return 0;
}

int find(double* a, int b, int e, double t)
{
	int mid = (b + e) / 2;
	int r = fcmp(a[mid], t);
	if(r == 0) return mid;
	else if(r > 0) return find(a, b, mid, t);
	else return find(a, mid+1, e, t);
}
inline int fcmp(double a, double b)
{
	if(b - a > eps) return -1;
	else if(a - b > eps) return 1;
	else return 0;
}