2014
11-05

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

#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;
}
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;
}


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

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

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

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