放牧代码和思想
专注自然语言处理、机器学习算法
    Why join the Navy if you can be a pirate?

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//////////////////////////////////
13888320 hankcs 3168 Accepted 3348K 547MS C++ 2543B 2015-02-14 04:50:02

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

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机