#include #include #include #include #include #include using namespace std; typedef complex cplx; class union_find{ public: union_find(int n){ for (int i=0;i dat; }; struct point{ point(){} point(double x,double y,double z):x(x),y(y),z(z){} double x,y,z; }; pair cross_sphere(pair &c1,pair &c2) { double za = c1.first.z; double zb = c2.first.z; double r = c1.second, s = c2.second; double dx = c1.first.x - c2.first.x; double dy = c2.first.y - c1.first.y; double l = sqrt(dx*dx + dy*dy); cplx a(0,za),b(l,zb); if(norm(b-a)<=0.000001) return make_pair(-100000,+100000); double zx = 0.5*(1+(r*r-s*s)/norm(b-a)); double rooter = r*r/norm(b-a) - zx*zx; if(rooter<0) return make_pair(-100000,+100000); double zy = sqrt(rooter); cplx z (zx,zy); double z1 = za+imag(z*(b-a)); double z2 = za+imag(conj(z)*(b-a)); return make_pair(z1,z2); } bool cross_circle(pair &c1,pair &c2) { double dx=c1.first.x-c2.first.x; double dy=c1.first.y-c2.first.y; double d=sqrt(dx*dx+dy*dy); return (d>n,n!=0){ vector > dat(n); set zs; zs.insert(100000); zs.insert(-100000); for (int i=0;i>p.x>>p.y>>p.z>>r; dat[i]=make_pair(p,r); zs.insert(p.z+r); zs.insert(p.z-r); } for (int i=0;i cross=cross_sphere(dat[i],dat[j]); zs.insert(cross.first); zs.insert(cross.second); } } vector nums; set::iterator p,q; p=zs.begin(); q=p;q++; while(q!=zs.end()){ double z=(*p+*q)/2; vector > cs; for (int i=0;i tmp; for (int i=0;i