首页 > ACM题库 > HDU-杭电 > HDU 4214-Crash and Go(relians)-计算几何-[解题报告]HOJ
2015
05-23

HDU 4214-Crash and Go(relians)-计算几何-[解题报告]HOJ

Crash and Go(relians)

问题描述 :

The Gorelians are a warlike race that travel the universe conquering new worlds as a form of recreation. Generally, their space battles are fairly one-sided, but occasionally even the Gorelians get the worst of an encounter. During one such losing battle, the Gorelians’ space ship became so damaged that the Gorelians had to evacuate to the planet below. Because of the chaos (and because escape pods are not very accurate) the Gorelians were scattered across a large area of the planet (yet a small enough area that we can model the relevant planetary surface as planar, not spherical). Your job is to track their efforts to regroup. Fortunately, each escape pod was equipped with a locator that can tell the Gorelian his current coordinates on the planet, as well as with a radio that can be used to communicate with other Gorelians. Unfortunately, the range on the radios is fairly limited according to how much power one has.
When a Gorelian lands on the alien planet, the first thing he does is check the radio to see if he can communicate with any other Gorelians. If he can, then he arranges a meeting point with them, and then they converge on that point. Once together, they are able to combine the power sources from their radios, which gives them a larger radio range. They then repeat the process―see who they can reach, arrange a meeting point, combine their radios―until they finally cannot contact any more Gorelians.
Gorelian technology allows two-way communication as long as at least one of them has a radio with enough range to cover the distance between them. For example, suppose Alice has a radio with a range of 40 km, and Bob has a range of 30 km, but they are 45 km apart (Figure 1). Since neither has a radio with enough range to reach the other, they cannot talk. However, suppose they were only 35 km apart (Figure 2). Bob’s radio still does not have enough range to reach Alice, but that does not matter―they can still talk because Alice’s radio has enough range to reach Bob.
Sokoban
   

Sokoban


If a Gorelian successfully contacts other Gorelians, they will meet at the point that is the average of all their locations. In the case of Alice and Bob, this would simply be the midpoint of A and B (Figure 3). Note that the Gorelians turn off their radios while traveling; they will not attempt to communicate with anyone else until they have all gathered at the meeting point. Once the Gorelians meet, they combine their radios to make a new radio with a larger range. In particular, the area covered by the new radio is equal to the sum of the areas covered by the old radio. In our example, Alice had a range of 40 km, so her radio covered an area of 1600π km. Bob’s radio covered an area of 900π km. So when they combine their radios they can cover 2500π km―meaning they have a range of 50 km. At this point they will try again to contact other Gorelians.
Sokoban
   

Sokoban


This process continues until no more Gorelians can be contacted. As an example, suppose the following Gorelians have all landed and all have a radio range of 30 km: Alice (100, 100), Bob (130, 80), Cathy (80, 60), and Dave (120, 150). At this point, none of the Gorelians can contact anyone else (Figure 5). Now Eddy lands at position (90, 80) (Figure 6). Eddy can contact Alice and Cathy, so they arrange to meet at (90, 80), which is the average of their locations. Combining their radios gives them a range of √2700 ≈ 51.96 km (Figure 7).
Sokoban
   

Sokoban


Now they check again with their new improved range and find that they can reach Bob. So they meet Bob at (110, 80) and combine their radios to get a new radio with a range of 60 (Figure 8). Unfortunately, this is not far enough to be able to reach Dave, so Dave remains isolated.
Sokoban
   

Sokoban

输入:

The input will consist of one or more data sets. Each data set will begin with an integer N representing the number of Gorelians for this dataset (1 ≤ N ≤ 100). A value of N = 0 will signify the end of the input.
Next will come N lines each containing three integers X, Y, and R representing the x- and y-coordinate where the Gorelian lands and the range of the radio (0 ≤ X ≤ 1000, 0 ≤ Y ≤ 1000, and 1 ≤ R ≤ 1000). Note that only the Gorelians’ initial coordinates/range will be integral; after merging with other Gorelians they may no longer be integral. You should use double-precision arithmetic for all computations.
The Gorelians land in the order in which they appear in the input file. When a Gorelian lands, he merges with any Gorelians he can contact, and the process keeps repeating until no further merges can be made. The next Gorelian does not land until all previous merges have been completed.

输出:

The input will consist of one or more data sets. Each data set will begin with an integer N representing the number of Gorelians for this dataset (1 ≤ N ≤ 100). A value of N = 0 will signify the end of the input.
Next will come N lines each containing three integers X, Y, and R representing the x- and y-coordinate where the Gorelian lands and the range of the radio (0 ≤ X ≤ 1000, 0 ≤ Y ≤ 1000, and 1 ≤ R ≤ 1000). Note that only the Gorelians’ initial coordinates/range will be integral; after merging with other Gorelians they may no longer be integral. You should use double-precision arithmetic for all computations.
The Gorelians land in the order in which they appear in the input file. When a Gorelian lands, he merges with any Gorelians he can contact, and the process keeps repeating until no further merges can be made. The next Gorelian does not land until all previous merges have been completed.

样例输入:

5
100 100 30
130 80 30
80 60 30
120 150 30
90 80 30
6
100 100 50
145 125 10
60 140 15
160 145 20
130 135 25
80 80 30
0

样例输出:

2
3

/*
hdu 4214 Crash and Go(relians)
题意:伞兵降落到一个星球上,每个人带着一个电台,只要任何一方进入另一方的覆盖范围,双方就可以沟通
练习到所有可以联系的战友,他们会在一个点()回合,用他们的电台合成一个功率更大的电台,新电台的覆盖面积是那些的和
一直这样合并下去,问最后剩下几个电台

所给数据的顺序就是伞兵落地的顺序,只有落地后才能打开电台


*/
#include<stdio.h>
#include<list>
#include<cmath>
#include<iostream>
using namespace std;
struct node//描述一个电台 的坐标和 覆盖半径
{
	double a,b,r;
};
int he(node &nod,list<node> &ll)
{
	int flag=0;//可合并的个数
	double a=0,b=0,rr=0;
	list<node>::iterator it;
	it=ll.begin();
	while(it!=ll.end())
	{
		double ma=it->a,mb=it->b,mr=it->r;
		double dist=sqrt((nod.a-ma)*(nod.a-ma)+(nod.b-mb)*(nod.b-mb));
		if(dist>mr&&dist>nod.r)//任何一方都未进入另一方的覆盖范围
		{
			it++;
			continue;
		}else
		{
			a+=ma;//收集可合并的信息
			b+=mb;
			rr+=mr*mr;
			flag++;
			it=ll.erase(it);//删除这个电台
		}
	}
	if(flag)//若可合并
	{
		flag++;
		a+=nod.a;
		b+=nod.b;
		rr+=nod.r*nod.r;

		
		a=a/flag;
		b=b/flag;
		rr=sqrt(rr);
		nod.a=a;//合并成新的电台
		nod.b=b;
		nod.r=rr;

		return 1;
	}else
	{
		return 0;//否则返回0,表示不能合并
	}
}
int main()
{
	int n,i;
	double a,b,rr;
	while(cin>>n,n)
	{
		list<node> ll;
		
		node nod;
		for(i=1;i<=n;++i)
		{
			int flag=0;
			a=b=rr=0;
			cin>>nod.a>>nod.b>>nod.r;//读入一个电台(士兵)的信息
			while(he(nod,ll))//尝试与其他的电台合并,若合并成功,拿新的电台再次尝试
				;//这儿什么都不做
			ll.push_back(nod);//把这个电台放到这里边
		}
		cout<<ll.size()<<endl;
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/qq172108805/article/details/8764760