#include #include #include #include #include #include #include using namespace std ; typedef pair pii ; struct pt { double x, y, z ; void show() const { cout << x << "," << y << "," << z ; } } ; struct pt2 { double x, y ; double z() const { return x*x + y*y ; } } ; bool operator<(const pt &a, const pt &b) { return a.x != b.x ? a.x < b.x : a.y != b.y ? a.y < b.y : a.z < b.z ; } pt midpoint(const pt &a, const pt &b) { return pt({0.5*(a.x+b.x), 0.5*(a.y+b.y), 0.5*(a.z+b.z)}) ; } pt mul(const pt &a, double sc) { return pt({sc*a.x, sc*a.y, sc*a.z}) ; } pt vec(const pt &a, const pt &b) { return pt({b.x-a.x, b.y-a.y, b.z-a.z}) ; } pt normalize(const pt &a) { return mul(a, 1.0/sqrt(a.x*a.x+a.y*a.y+a.z*a.z)) ; } double dot(const pt &a, const pt &b) { return a.x*b.x + a.y*b.y + a.z*b.z ; } pt cross(const pt &a, const pt &b) { return pt({a.y*b.z-a.z*b.y, a.z*b.x-a.x*b.z, a.x*b.y-a.y*b.x}) ; } pt normal(const pt &a, const pt &b, const pt &c) { pt ab = vec(a, b) ; pt ac = vec(a, c) ; return cross(ab, ac) ; } pt norm(const pt &a, const pt &b, const pt &c) { return normalize(normal(a, b, c)) ; } vector pts ; map tris ; struct circle { pt2 c ; double r ; double area() { return r * r * M_PI ; } } ; double fudge = 1 + 1e-10 ; pt2 midpoint(const pt2 &a, const pt2 &b) { return pt2({0.5*(a.x+b.x), 0.5*(a.y+b.y)}) ; } double dist(const pt2 &a, const pt2 &b) { return hypot(a.x-b.x, a.y-b.y) ; } bool incirc(const circle c, const pt2 &p) { return dist(c.c, p) <= c.r * fudge ; } /** * Given three points, find the single circle that goes through * all three. */ circle circle3(const pt2 &ci, const pt2 &cj, const pt2 &ck) { double xij = ci.x - cj.x ; double xjk = cj.x - ck.x ; double yij = ci.y - cj.y ; double yjk = cj.y - ck.y ; double zij = ci.z() - cj.z() ; double zjk = cj.z() - ck.z() ; double det = 2 * (xij * yjk - xjk * yij) ; if (det == 0) return circle({0,0,-1}) ; double x = (zij * yjk - zjk * yij) / det ; double y = (xij * zjk - xjk * zij) / det ; double r = hypot(x-ci.x, y-ci.y) ; return circle({x, y, r}) ; } /** * We know two points that must be on the boundary. * Return the appropriate bounding circle. We can move left or we * can move right but we cannot move both directions. */ circle boundingcircle2(vector &pts, int j, int k) { circle c ; c.c = midpoint(pts[j], pts[k]) ; c.r = dist(c.c, pts[j]) ; for (int i=0; i sofar ; circle boundingcircle1(vector &pts, int j) { int k = 0 ; if (k == j) k++ ; circle c ; c.c = midpoint(pts[j], pts[k]) ; c.r = dist(c.c, pts[j]) ; sofar.clear() ; sofar.push_back(pts[j]) ; sofar.push_back(pts[k]) ; for (int i=0; i &pts) { random_shuffle(pts.begin(), pts.end()) ; circle c ; c.c = midpoint(pts[0], pts[1]) ; c.r = dist(c.c, pts[0]) ; vector sofar ; for (int i=0; i> n ; double xs=0, ys=0, zs=0 ; for (int i=0; i> x >> y >> z ; pts.push_back(pt({x, y, z})) ; xs += x ; ys += y ; zs += z ; } xs /= n ; ys /= n ; zs /= n ; pt center({xs, ys, zs}) ; int boti = 0 ; for (int i=1; i q ; // cout << "Starting with " << boti << " " << botj << endl ; q.push_back(make_pair(boti, botj)) ; vector onhull(n) ; for (int qg=0; qg hiv) { hiv = v ; hii = i ; } if (v < lov) { lov = v ; loi = i ; } } if (tris.find(lin) == tris.end()) { tris[lin] = hii ; q.push_back(make_pair(lin.second, hii)) ; q.push_back(make_pair(hii, lin.first)) ; } if (tris.find(lin2) == tris.end()) { tris[lin2] = loi ; q.push_back(make_pair(lin2.second, loi)) ; q.push_back(make_pair(loi, lin2.first)) ; } } vector hullpts ; for (int i=0; i 1) cout << "Points " << hullpts.size() << " triangles " << tris.size() / 3.0 << " edges " << tris.size() / 2.0 << endl ; int nn = hullpts.size() ; double r = 1e99 ; for (auto it = tris.begin(); it != tris.end(); it++) { pii lin = it->first ; int p3 = it->second ; // cout << "pt " << lin.first << " " << lin.second << " " << p3 << endl ; if (p3 > lin.first && p3 > lin.second) { /* cout << "Points are " ; pts[lin.first].show() ; cout << " " ; pts[lin.second].show() ; cout << " " ; pts[p3].show() ; cout << endl ; */ pole = norm(pts[lin.first], pts[lin.second], pts[p3]) ; pt polex ; if (pole.x != 0 || pole.y != 0) { polex = normalize(pt({-pole.y, pole.x, 0})) ; } else { polex = normalize(pt({0, -pole.z, pole.y})) ; } pt poley = normalize(cross(pole, polex)) ; double hiv = dot(pole, hullpts[0]) ; double lov = hiv ; vector circ ; for (int i=0; i 1) cout << "See " << vol << " from " << (hiv-lov) << " " << c.area() << endl ; r = min(vol, r) ; } } cout << setprecision(15) << r << endl ; }