2014
03-06

Beacons

In ancient times, communication was not as swift as it is today. When a kingdom was at war, it could take months to muster all the armed forces. But by using fire-lit beacons at strategic locations, it was still possible to quickly send emergency signals.

When the first beacon is lit, all other beacons within sight from it are also lit. All beacons within sight of these are then lit, and so on until all beacons are lit – assuming of course that all beacons are within sight of each other, directly or indirectly. If they are not, the dire news must be carried by riders between some beacons.

Given the location of all beacons in the kingdom as well as the location and size of all mountain peaks, write a program that determines how many messages must be sent by riders in order for all beacons to be lit when an enemy threatens the country.

For simplicity, we model the country in the following way: a beacon is represented as a point in the xy-plane and a mountain peak is represented as a circle. Two beacons are considered to be within sight of each other if no mountain peak blocks the straight line between the two beacons.

The input will be constructed so that the straight line between any pair of beacons will not touch the circumference of a mountain peak, unless it passes through the interior of another mountain peak. Mountain peaks will not overlap or touch, nor will any beacon be on a mountain peak or on its circumference.

The first line in the input contains two integers n (1 <= n <= 1000) and m (0 <= m <= 1000) the number of beacons and the number of mountain peaks, respectively. Then follow n lines specifying the locations of the beacons. The location of each beacon is given as a pair of integers x and y (0 <= x, y <= 10000). Then follow m lines describing the mountain peaks. Each mountain peak is given as a pair of integers x and y (0 <= x, y <= 10000) specifying the location of the peak and a radius r (1 <= r <= 5000).

The first line in the input contains two integers n (1 <= n <= 1000) and m (0 <= m <= 1000) the number of beacons and the number of mountain peaks, respectively. Then follow n lines specifying the locations of the beacons. The location of each beacon is given as a pair of integers x and y (0 <= x, y <= 10000). Then follow m lines describing the mountain peaks. Each mountain peak is given as a pair of integers x and y (0 <= x, y <= 10000) specifying the location of the peak and a radius r (1 <= r <= 5000).

6 3
1 8
5 4
7 7
9 2
16 6
17 10
4 7 2
6 3 1
12 6 3
4 4
0 4
8 4
4 0
4 8
2 2 1
6 2 1
2 6 1
6 6 1

2
1

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
map<int,int> s;
map<int,int>::iterator it;
double eps=1e-10;
int n,m;
const double pi=acos(-1.0);
int fa[1001],x[1001],y[1001],cx[1001],cy[1001],r[1001];
struct Eve
{
double ang;
int id,L,f;
bool operator<(const Eve &b)const
{
if(fabs(ang-b.ang)>eps)return ang<b.ang;
return f>b.f;
}
}p[8001];
int find(int x)
{
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
void U(int i,int j)
{
fa[find(i)]=find(j);
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=0;i<n;i++){scanf("%d%d",x+i,y+i);fa[i]=i;}
for(int i=0;i<m;i++)scanf("%d%d%d",cx+i,cy+i,r+i);
if(m==0){puts("0");continue;}
for(int i=0;i<n;i++)
{
int t=0;
for(int j=i+1;j<n;j++)
{
p[t].ang=atan2((double)(y[j]-y[i]),(double)(x[j]-x[i]));
if(p[t].ang<-eps)p[t].ang+=pi*2;
p[t].id=j;
p[t].L=(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]);
p[t++].f=0;
}
for(int j=0;j<m;j++)
{
double th=atan2((double)(cy[j]-y[i]),(double)(cx[j]-x[i]));
int d=(cx[j]-x[i])*(cx[j]-x[i])+(cy[j]-y[i])*(cy[j]-y[i]);
double dt=asin((double)r[j]/sqrt((double)d));
int ds=d-r[j]*r[j];
double u=th-dt,v=th+dt;
if(u<0)u+=pi*2,v+=pi*2;
if(v<pi*2+eps)
{
p[t].L=ds;
p[t].ang=u;
p[t++].f=1;
p[t].L=ds;
p[t].ang=v;
p[t++].f=-1;
}
else
{
p[t].L=ds;
p[t].ang=u;
p[t++].f=1;
p[t].L=ds;
p[t].ang=pi*2;
p[t++].f=-1;

p[t].L=ds;
p[t].ang=0;
p[t++].f=1;
p[t].L=ds;
p[t].ang=v-pi*2;
p[t++].f=-1;
}
}
sort(p,p+t);
s.clear();
for(int j=0,tot=0;j<t;j++)
{
if(p[j].f==0)
{
if(tot==0)U(i,p[j].id);
else
{
it=s.begin();
if(it->first>p[j].L)U(i,p[j].id);
}
}
else if(p[j].f==1)
{
s[p[j].L]++;
++tot;
}
else
{
s[p[j].L]--;
if(s[p[j].L]==0)s.erase(p[j].L);
--tot;
}
}
}
int cnt=0;
for(int i=0;i<n;i++)if(find(i)==i)++cnt;
printf("%d\n",--cnt);
}
}

1. 女孩走在回家的路上、今天是她妈妈的生日、她手里提着给她妈妈的生日礼物、小嘴里哼着即将唱给她妈妈的生日快乐歌、她渴望能和家人幸幸福福的过日子、但是、造化弄人、她走过一条小巷、前面走过来三个三十左右的男人。看样子他们是喝了很多 女孩小心的低下头、当走过他们身

2. 难道整个南方不装暖气不安空调也怪天气冷？你们不弄保温层就罢了，不安暖气也算了，夏天那个空调就能制冷？ 唯一俩可能一就是穷，二就是矫情，在电脑前边冷的发抖边说哎呀，南方气温下降到0°C啦，冻死了。

3. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

4. 您没有考虑 树的根节点是负数的情况， 若树的根节点是个很大的负数，那么就要考虑过不过另外一边子树了