首页 > ACM题库 > HDU-杭电 > HDU 3511-Prison Break-线段树-[解题报告]HOJ
2014
11-05

HDU 3511-Prison Break-线段树-[解题报告]HOJ

Prison Break

问题描述 :

To save Sara, Michael Scofield was captured by evil policemen and he was arrested in Prison again. As is known to all, nothing can stop Michael, so Prison Break continues.
The prison consists of many circular walls. These walls won’t intersect or tangent to each other.

Now Michael is arrested in one of the deepest rooms, and he wants to know how many walls he has to break at least for running out. In figure 1, Michael has to break 3 walls at least and in figure 2, 2 walls are needed.

输入:

There will be multiple test cases (no more than 10) in a test data.
For each test case, the first line contains one number: n (1<=n<=50,000) indicating the total number of circular walls.
Then n lines follow, each line contains three integers x, y, r. (x,y) indicates the center of circular wall and r indicates the radius of the wall.
-100,000<=x,y<=100,000
1 <= r <= 100,000
The input ends up with EOF.

输出:

There will be multiple test cases (no more than 10) in a test data.
For each test case, the first line contains one number: n (1<=n<=50,000) indicating the total number of circular walls.
Then n lines follow, each line contains three integers x, y, r. (x,y) indicates the center of circular wall and r indicates the radius of the wall.
-100,000<=x,y<=100,000
1 <= r <= 100,000
The input ends up with EOF.

样例输入:

3
0 0 1
0 0 2
0 0 3
3
0 0 10
5 0 1
-5 0 1

样例输出:

3
2

今天纠结了这一个,最终还是看题解过的。

不过还是学到蛮多东西的。

这个题是给你N个圆,求最多嵌套次数。

第一反应是DP啊,因为以前做过一道题,矩形嵌套(看这里),那个题其实就是最长XX子序列了,我想啊,那这个题按半径排序后不也可以用最长XX子序列么。

不同的是,这里的N比较大,用一般XX子序列的N^2做法会超时的,所以想到单调队列优化了。但是鉴于本人搓得要死的DP,我只知道单调队列能让它时间复杂度降到N*LOGN,但是具体不会实现。然后和CG,CW讨论了下,CW想出来个很麻烦,但是平均时间是N*LOGN的,但是这是最好情况貌似 = =。。。反正这个题用单调队列会很难搞。好吧。

网上还有人用随机乱搞 = =。。。这个数据比较小,如果数据量大点,用随机根本不行 = =。。ym下RP好的。

剩下的基本都一样了,用扫描线搞。

还有个想法(不过后来证实有BUG),用线段树搞。类似矩形求交,把每个圆想成一个正方形,然后扫一遍,在对应的线段上标记。下个圆如果全部包含在标记的区域内,那么说明这个圆在之前的圆里,求个最小值,整体求最大值。有BUG,见下图。按我那种做法,这种情况我的结果是2 = =。。。测了下数据,发现真的有两组过不去。。崩溃。

Prison Break

好了。其他就是官方解法了。http://www.cppblog.com/superlong/archive/2010/08/06/122427.html

为次专门学了下set,好伟大的STL。。其他不多说了,好好看看,好好琢磨 = =。。

附copy代码 = = 。。我真是个挫人。。。

#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define BUG puts("here!!!")

using namespace std;

const int MAX = 100010;
int X;
struct circle{ int w,x,y,r;};
circle c[MAX];

double yy(int id,int flag)
{
	double d = sqrt(c[id].r*1.0*c[id].r - (X-c[id].x)*1.0*(X-c[id].x));
	if( flag == 1 ) return c[id].y + d;
	return c[id].y - d;
}

struct Sline{
	int flag,id;
	bool operator<(const Sline a)const
	{
		double y1 = yy(id, flag);
		double y2 = yy(a.id, a.flag);
		return y1 > y2 || y1 == y2 && flag > a.flag;		
	}
};

set<Sline> s;
set<Sline>::iterator pre,suc,it;

struct event{ int x,id,flag;};
event l[MAX];

bool cmp(event a,event b)
{
	if( a.x == b.x )
		return c[a.id].y > c[b.id].y;
	return a.x < b.x;
}

void add_line(circle c, int &cnt ,int id)
{
	l[cnt].id = id;
	l[cnt].x = c.x - c.r;
	l[cnt++].flag = 1;
	l[cnt].id = id;
	l[cnt].x = c.x + c.r;
	l[cnt++].flag = -1;
}


void solve(int n)
{
	s.clear();
	Sline node;
	for(int i=0; i<n; i++)
	{
		X = l[i].x;
		if( l[i].flag == 1 )
		{
			node.id = l[i].id; node.flag = 1;
			it = s.insert(node).first;
			suc = pre = it;
			suc++;
			if( it == s.begin() || suc == s.end() )
				c[it->id].w = 1;
			else
			{
				pre--;
				if( pre->id == suc->id )
					c[it->id].w = c[pre->id].w + 1;
				else
					c[it->id].w = max( c[pre->id].w, c[suc->id].w);
			}
			node.flag = -1;
			s.insert(node);
		}
		else
		{
			node.id = l[i].id; node.flag = 1;
			s.erase(node);
			node.flag = -1;
			s.erase(node);
		}
	}
}
int main()
{
	int ncases,n;
	int x1,x2,y1,y2,xx,yy,r;
	
	while( ~scanf("%d",&n) )
	{
		int cnt = 0;
		for(int i=0; i<n; i++)
		{
			scanf("%d%d%d",&c[i].x, &c[i].y, &c[i].r);
			c[i].w = 0;
			add_line(c[i],cnt,i);
		}
		sort(l,l+cnt,cmp);
		
		solve(cnt);
		
		int ans = 0;
		for(int i=0; i<n; i++)
			ans = max(ans, c[i].w);
		printf("%d\n",ans);
	}

return 0;
}

参考:http://blog.csdn.net/zxy_snow/article/details/6689453


  1. 第一点:我觉得那迷烟应该是一种植物或者花草,那种东西应该是让人闻到,要么就是性格转变,要么就是另某人沉迷于一种事

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  4. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  5. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。