放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理,大约每周末一次。另外,不要叫我楼主,谢谢。

POJ 3293 Rectilinear polygon 题解 《挑战程序设计竞赛》

目录

POJ 3293 Rectilinear polygon

直角多边形:给定N个点,问是否能组成直角多边形(每个顶点都与另外两个顶点构成直角,每条边都平行于坐标轴),并求出周长?

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

平面扫描 

扫描线移动时,如果线上的点数为偶数,则相邻两个点构成一条边,记录下来;如果为奇数,则无法构成(余下一个点无法构成边)。切换扫描线到另一坐标轴,执行相似的逻辑,不过还需检查横向的边是否与纵向的边相交,如果相交,则无法构成。

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX_N 100000 + 16

int link_x[MAX_N],		// 水平方向相连的顶点
link_y[MAX_N];			// 垂直方向相连的顶点

struct Point
{
	int x, y;
	int id;
	int get(const bool& is_x)
	{
		return is_x ? x : y;
	}
	int get_link(const bool& is_x)
	{
		return is_x ? link_x[id] : link_y[id];
	}
	void link(const bool& is_x, const Point& to)
	{
		(is_x ? link_x[id] : link_y[id])	   = to.id;
		(is_x ? link_x[to.id] : link_y[to.id]) = id;
	}
}ps[MAX_N];

struct Line
{
	int x, y1, y2;
	Line(){}
	Line(int x, int y1, int y2) :x(x), y1(y1), y2(y2){}
}ls[MAX_N];

bool is_x;
int cmp(Point& a, Point& b)
{
	int ax = a.get(is_x);
	int bx = b.get(is_x);
	int ay = a.get(!is_x);
	int by = b.get(!is_x);
	if (ax == bx) return ay < by;
	return ax < bx;
}

bool check_intersect(const Point& a, const Point& b, const int& ln)
{
	int y = a.y, x1 = a.x, x2 = b.x;
	for (int i = 0; i < ln; i++)
	{
		if (x1 < ls[i].x && x2 > ls[i].x && ls[i].y1 < y && ls[i].y2 > y)
			return true;
	}
	return false;
}

int M, N;
int traverse(int& ln)
{
	sort(ps, ps + N, cmp);
	int count_same_line = 1;
	int sum = 0;
	for (int i = 1; i < N; ++i)
	{
		if (ps[i].get(is_x) != ps[i - 1].get(is_x))
		{
			// 扫描线移动
			if (count_same_line & 1)
			{
				return -1;
			}
			count_same_line = 1;
		}
		else
		{
			// 同一条扫描线上的点遍历
			++count_same_line;
			if (!(count_same_line & 1))
			{
				sum += ps[i].get(!is_x) - ps[i - 1].get(!is_x);
				ps[i].link(is_x, ps[i - 1]);
				if (is_x)
				{
					// 横向扫描记录竖向直线
					ls[ln++] = Line(ps[i].x, ps[i - 1].y, ps[i].y);
				}
				else
				{
					// 竖向扫描检查是否相交
					if (check_intersect(ps[i - 1], ps[i], ln))
					{
						return -1;
					}
				}
			}
		}
	}
	return sum;
}

int solve()
{
	int ln = 0;
	is_x = true;
	int x = traverse(ln);
	if (x == -1) return -1;
	is_x = false;
	int y = traverse(ln);
	if (y == -1) return -1;
	int cur = 0;
	int link_count = 0;
	do
	{
		cur = is_x ? link_x[cur] : link_y[cur];
		is_x = !is_x;
		++link_count;
	} while (cur != 0);
	if (link_count != N)
	{
		return -1;
	}
	return x + y;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	scanf("%d", &M);
	while (M--)
	{
		scanf("%d", &N);
		for (int i = 0; i < N; ++i)
		{
			scanf("%d%d", &ps[i].x, &ps[i].y);
			ps[i].id = i;
		}
		printf("%d\n", solve());
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////
13890173 hankcs 3293 Accepted 760K 250MS C++ 2743B 2015-02-14 23:59:14

如果你忘了做相交检查的话,以下用例会输出错误结果16:

1
6
0 0
1 0
0 1
2 1
1 2
2 2

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

分享到:更多 ()

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    其实把X方向优先排一次序,再把Y方向优先排一次序,可行解在这两个数组是中间就已经是相邻顶点了.
    关于相交的问题,因为在处理Y方向的时候X方向也排序好了,所以只需要二分查找当前横线段的左右端点间的竖线段判断相交,最后一个DFS就行,时间比楼主快,47MS

    潘俊臣1年前 (2016-06-11)回复

我的开源项目

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