HDU 1542 Atlantis

题目链接

题意：给定一些矩形，求面积并

思路：利用扫描线，因为这题矩形个数不多，直接暴力扫就能够了。假设数据大。就要用线段树

代码：

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int N = 205;

const int M = 100005;

const double eps = 1e-8;

int n, vis[N], hn;

double hash[N];

struct Line {

	double l, r, y;

	int flag;

	Line() {}

	Line(double l, double r, double y, int flag) {

		this->l = l;

		this->r = r;

		this->y = y;

		this->flag = flag;

	}

} line[N];

bool cmp(Line a, Line b) {

	return a.y < b.y;

}

int get(double x) {

	return lower_bound(hash, hash + hn, x) - hash;

}

int main() {

	int cas = 0;

	while (~scanf("%d", &n) && n) {

		double x1, x2, y1, y2; hn = 0;

		memset(vis, 0, sizeof(vis));

		for (int i = 0; i < n; i++) {

			scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);

			line[i * 2] = Line(x1, x2, y1, 1);

			line[i * 2 + 1] = Line(x1, x2, y2, -1);

			hash[hn++] = x1; hash[hn++] = x2;

		}

		n *= 2;

		sort(line, line + n, cmp);

		sort(hash, hash + hn);

		hn = 1;

		for (int i = 1; i < n; i++) {

			if (fabs(hash[i] - hash[i - 1]) < eps) continue;

			hash[hn++] = hash[i];

		}

		double ans = 0;

		for (int i = 0; i < n; i++) {

			int l = get(line[i].l), r = get(line[i].r);

			double len = 0;

			for (int j = 0; j < hn - 1; j++) if (vis[j] > 0) len += (hash[j + 1] - hash[j]);

			if (i) ans += len * (line[i].y - line[i - 1].y);

			for (int j = l; j < r; j++) vis[j] += line[i].flag;

		}

		printf("Test case #%d\n", ++cas);

		printf("Total explored area: %.2lf\n\n", ans);

	}

	return 0;

}