AOJ 1255 Inherit the Spheres

問題

3次元空間に球がいくつかある。
空間を平面z = aで切ったときに、
球と平面の交点は円になるが、その円いくつの連結成分にわかれているか、
z = 0からz = 36000まで、連結成分の個数の変化を出力せよ。

制約条件

n≦100

方針

平面が各球の上下に接する時のz座標、
二球の交わりの部分のうち、最大のz座標と最小のz座標を全て考えればいい。

二球の交わりの部分のz座標の最大値と最小値は、
二球を、一つの球を中心として、z軸についてもう片方の球を回転させてy座標を0にしたときの
xz平面での二円の交わりを見ればいい。

それぞれのz座標のときに、円の連結成分の個数を求めるのは、
適当にunion findしてやればよい。（ワーシャルフロイドだとTLEした）

ソースコード

double d3(double x, double y, double z){
	return sqrt(x * x + y * y + z * z);
}
int n;
vector<double> x, y, z, r;
vector<double> zs;

bool v[100];
int p[100];
double tr[100];
inline int root(int x){
	if(x == p[x]) return x;
	return root(p[x]);
}
inline void merge(int a, int b){
	a = root(a); b = root(b);
	if(a != b) p[a] = b;
}
int calc(double h){
	rep(i, n){
		if(abs(abs(z[i] - h) - r[i]) < EPS)
			tr[i] = 0;
		else if(abs(z[i] - h) < r[i] + EPS)
			tr[i] = sqrt(r[i] * r[i] - (z[i] - h) * (z[i] - h) + EPS);
		else tr[i] = -1;
	}
	int res = 0;
	rep(i, n) p[i] = i, v[i] = 0;
	rep(i, n) rep(j, n) if(i != j && tr[i] >= 0 && tr[j] >= 0){
		if(abs(P(x[i] - x[j], y[i] - y[j])) < tr[i] + tr[j] + EPS)
			merge(i, j);
	}
	rep(i, n) if(tr[i] >= 0){
		int a = root(i);
		if(!v[a]) v[a] = 1, res++;
	}
	return res;
}

int main(){
  while(cin >> n, n){
  	x.clear(); y.clear(); z.clear(); r.clear();
  	rep(i, n){
  		double a, b, c, d;
  		cin >> a >> b >> c >> d;
  		x.pb(a); y.pb(b); z.pb(c); r.pb(d);
  		zs.pb(c - d); zs.pb(c + d);
		}
		
		rep(i, n) rep(j, i) if(i != j)
			if(d3(x[i] - x[j], y[i] - y[j], z[i] - z[j]) < r[i] + r[j] + EPS){
			double dxy = abs(P(x[i] - x[j], y[i] - y[j]));
			P p1 = P(0, z[i]), p2 = P(dxy, z[j]);
			pair<P, P> ps = circle_circle_intersect(p1, r[i], p2, r[j]);
			zs.pb(ps.first.imag());
			zs.pb(ps.second.imag());
		}
		
		zs.pb(0); zs.pb(36000);
		sort(all(zs));
		vector<double> nzs;
		rep(i, zs.size()){
			if(i == 0 || zs[i] > zs[i-1] + EPS) nzs.pb(zs[i]);
		}
		string ans;
		int a;
		rep(i, nzs.size() - 1){
			int b = calc((nzs[i] + nzs[i+1]) / 2);
			if(i){
				if(a == b) ;
				else if(a < b) ans.pb('1');
				else ans.pb('0');
			}
			a = b;
		}
		cout << ans.size() << endl;
		cout << ans << endl;
	}
  return 0;
}