CSU 1857 Crash and Go(relians)(模拟)

Crash and Go(relians)

【题目类型】模拟

&题解：

这就是要严格的按照题意说的模拟就好了,也就是:每次添加进来一个圆,就找以前的,看有没有可以合成的多个圆,有的话就合成一起,这块要注意,合成之后,你一定要再从头跑一遍,因为合成之后的圆,有可能和之前联系不上的圆联系上了,所以这块就要多跑一个循环

【时间复杂度】(O(n^2))

&代码：

#include <cstdio>
#include <iostream>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
using ll=long long;
const int maxn= 1e2 +9;
int n;
struct po
{
	double x,y,r;
}te;
vector<po> vp;
double dis(po u,po v)
{
	return sqrt((u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y));
}
bool ok(po u,po v)
{
	return dis(u,v)<max(u.r,v.r);
}
void sol(int pos,vector<po>& tt)
{
	double x=0,y=0,r=0;
	for(int i=0;i<tt.size();i++){
		x+=tt[i].x;
		y+=tt[i].y;
		r+=tt[i].r*tt[i].r;
	}
	vp[pos].x=x/tt.size();
	vp[pos].y=y/tt.size();
	vp[pos].r=sqrt(r);
}
int main()
{
//	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	freopen("E:1.txt","r",stdin);
	while(cin>>n){
		if(n==0) break;
		vp.clear();
		for(int i=0;i<n;i++){
			double u,v,r;
			cin>>u>>v>>r;
			vp.push_back(po{u,v,r});
		}

		for(int i=0;i<n;i++) {
			vector<po> feasible;
			feasible.push_back(vp[i]);
			for(int j=0;j<i;j++) if(vp[j].r>0)
			{
//				if(i==4) printf("%d   ---
",j);
				if(ok(vp[i],vp[j])){
//				printf("=======  i=%d j=%d
",i,j);
					feasible.push_back(vp[j]);
					vp[j].r=-1;
				}
			}
			if(feasible.size()>1){
				sol(i,feasible);
				//这块就是新合成的一个圆 所以你要把它再循环一遍看之前有没有可以联系上的其他人
				i--;
			}
		}
		int ans=0;
		for(int i=0;i<n;i++){
//			printf("vp[%d] x=%f y=%f r=%f
",i,vp[i].x,vp[i].y,vp[i].r);
			if(vp[i].r>0) ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}