#include #include #include #include #include #include #define EPSILON (1e-12) #define LT(x,y) (((x)-(y)) <= -EPSILON) #define INC (1) #define DEC (0) using namespace std; typedef pair code_t; struct sphere_t { double x, y, z, r; }; struct circle_t { double x, y, r; circle_t(void) { } circle_t(double x, double y, double r) : x(x), y(y), r(r) { } }; double dist(double x0, double y0, double z0, double x1, double y1, double z1) { double dx = x1 - x0; double dy = y1 - y0; double dz = z1 - z0; return sqrt(dx * dx + dy * dy + dz * dz); } bool hide(const sphere_t &s, const sphere_t &t, int dir) { double d = dist(s.x, s.y, s.z + s.r * dir, t.x, t.y, t.z); return LT(d, t.r); } double solve(const sphere_t &s, const sphere_t &t, int dir) { if(hide(s, t, dir) || hide(t, s, dir)) return HUGE_VAL; double d = dist(s.x, s.y, s.z, t.x, t.y, t.z); if(LT(s.r + t.r, d)) return HUGE_VAL; double z0 = ((s.z + t.z) - (s.z - t.z) * (s.r - t.r) / d) / 2.0; double z1 = min(s.z * dir + s.r, t.z * dir + t.r) * dir; while(true) { double z = (z0 + z1) / 2.0; if(fabs(z0 - z1) < 1e-8) return z; double dz = dist(s.x, s.y, z, t.x, t.y, z); double rs = sqrt(s.r * s.r - (s.z - z) * (s.z - z)); double rt = sqrt(t.r * t.r - (t.z - z) * (t.z - z)); if(dz < rs + rt) z0 = z; else z1 = z; } } int countup(const vector &s, double z) { vector c; vector g; for(int i = 0; i < s.size(); i++) { if(LT(fabs(s[i].z - z), s[i].r)) { double r = sqrt(s[i].r * s[i].r - (s[i].z - z) * (s[i].z - z)); c.push_back(circle_t(s[i].x, s[i].y, r)); g.push_back(i); } } for(int i = 0; i < c.size(); i++) { for(int j = i + 1; j < c.size(); j++) { double d = dist(c[i].x, c[i].y, z, c[j].x, c[j].y, z); double r = c[i].r + c[j].r; if(LT(d, r)) { int s = min(g[i], g[j]); int t = max(g[i], g[j]); replace(g.begin(), g.end(), s, t); } } } sort(g.begin(), g.end()); return unique(g.begin(), g.end()) - g.begin(); } void append_code(const vector &s, vector &code, double z) { int n = countup(s, z - 1e-4); int m = countup(s, z + 1e-4); if(n < m) code.push_back(make_pair(z, INC)); if(n > m) code.push_back(make_pair(z, DEC)); } int main(void) { ifstream cin("H.txt"); int n; while(cin >> n) { if(n == 0) break; vector s(n); for(int i = 0; i < n; i++) { cin >> s[i].x >> s[i].y >> s[i].z >> s[i].r; } vector code; for(int i = 0; i < n; i++) { append_code(s, code, s[i].z - s[i].r); append_code(s, code, s[i].z + s[i].r); } for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { double zu = solve(s[i], s[j], +1); if(zu != HUGE_VAL) append_code(s, code, zu); double zl = solve(s[i], s[j], -1); if(zl != HUGE_VAL) append_code(s, code, zl); } } sort(code.begin(), code.end()); cout << code.size() << endl; for(int i = 0; i < code.size(); i++) cout << code[i].second; cout << endl; } return 0; }