POJ 3168 Barn Expansion 题解 《挑战程序设计竞赛》

POJ 3168 Barn Expansion

扩地：有N块不重叠的矩形地，由左下角（A,B）和右上角（C,D）决定。如果两块地的边或角相交，则两块地都无法扩大。求多少地可以扩大？

3.6与平面和空间打交道的计算几何 

平面扫描 

睡觉是什么能吃嘛？

如果一个点同时被两个或两个以上矩形共用，则这些矩形都无法扩大。由平行于X和Y的扫描线来扫描这些点，以平行于Y轴为例。如上图所示，将所有矩形的垂直边视作区间，两个端点按照X轴坐标、Y轴坐标、始末排序后得到上图结果：绿色为起始，红色为终止，编号为排序。

顺序由扫描线往上遍历区间，计算每个点的共享计数即可，也即为遇到起始共享计数+1，遇到终止共享计数-1。绿2点共享计数为2，这两个矩形都无法扩大了。

#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

enum PointType	// 端点类型
{
	START, END
};

struct Point
{
	int ord;	// 在当前轴上的坐标
	int pos;	// 在另一轴上的坐标
	int id;		// 是哪个矩形的角
	PointType type;	// 是起始还是结束

	Point()
	{}

	Point(int o, int p, int id, PointType t) : ord(o), pos(p), id(id), type(t)
	{}

	bool operator<(const Point &other) const
	{
		if (ord != other.ord)
			return ord < other.ord;
		if (pos != other.pos)
			return pos < other.pos;
		return type < other.type;	// 起点优先
	}
};

Point verticals[200000],  // 按照X优先排列的端点
horizontals[200000];	  // 按照Y优先排列的端点
int N;
bool ok[25000];

void traverse(const Point *start, const Point *end)
{
	int share_count = 0;	// 当前点被几个区间（几个矩形）共用
	const Point *t = start;
	int prev_ord = -1;
	bool invalid = false;	// 是否当前点已经扫过一次
	while (t != end)
	{
		if (t->ord != prev_ord)	// 扫描线移动了一下
		{
			share_count = 0;
			invalid = false;
			prev_ord = t->ord;
		}
		const int pos = t->pos;
		while (t != end && t->pos == pos && t->ord == prev_ord)
		{
			if (invalid)
				ok[t->id] = false;
			if (t->type == START)
			{
				++share_count;
				if (share_count >= 2)
					invalid = true;
			}
			if (t->type == END)
			{
				--share_count;
				if (share_count == 0)
					invalid = false;
			}
			++t;
		}
	}
}

void solve()
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i)
	{
		int A, B, C, D;
		scanf("%d %d %d %d", &A, &B, &C, &D);
		verticals[i * 4] = Point(A, B, i, START);			// 左下
		verticals[i * 4 + 1] = Point(A, D, i, END);		// 左上
		verticals[i * 4 + 2] = Point(C, B, i, START);		// 右下
		verticals[i * 4 + 3] = Point(C, D, i, END);		// 右上
		horizontals[i * 4] = Point(B, A, i, START);
		horizontals[i * 4 + 1] = Point(B, C, i, END);
		horizontals[i * 4 + 2] = Point(D, A, i, START);
		horizontals[i * 4 + 3] = Point(D, C, i, END);
	}
	sort(verticals, verticals + N * 4);
	sort(horizontals, horizontals + N * 4);
	memset(ok, 1, sizeof(ok));
	traverse(verticals, verticals + N * 4);
	traverse(horizontals, horizontals + N * 4);
	printf("%d\n", count(ok, ok + N, true));
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	solve();
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3168 Barn Expansion 题解 《挑战程序设计竞赛》