#include #include #include #include #include #include "validate.h" using namespace std; using i64 = long long; struct point { i64 x, y, z; point operator+(point p) { return {x+p.x, y+p.y, z+p.z}; } point operator-(point p) { return {x-p.x, y-p.y, z-p.z}; } bool operator==(point p) { return tie(x,y,z) == tie(p.x,p.y,p.z); } bool operator< (point p) { return tie(x,y,z) < tie(p.x,p.y,p.z); } }; point zero = {0,0,0}; i64 operator|(point a, point b) { // dot product return a.x*b.x + a.y*b.y + a.z*b.z; } point operator*(point a, point b) { // cross product return {a.y*b.z - a.z*b.y, a.z*b.x - a.x*b.z, a.x*b.y - a.y*b.x}; } i64 dist2(point a, point b) { // squared distance return (b-a)|(b-a); } bool colinear(point a, point b, point c) { return (b-a)*(c-a) == zero; } // Signed volume of the parallelepiped defined by vectors ab,ac,ad. // The result is positive iff ab,ac,ad form a right-handed coordinate system. // The result is zero iff all four points are coplanar. i64 orient(point a, point b, point c, point d) { return ((b-a)*(c-a)) | (d-a); } // Given a set of points, finds the volume of their convex hull. Works for any set of points. i64 convex_hull(vector p) { // First, remove all duplicates. sort(begin(p), end(p)); p.erase(unique(begin(p), end(p)), end(p)); int n = p.size(); // Filter 'middle' points of any colinear triplet. std::vector include(n, true); for (int a = 0; a < n; a++) { for (int b = a+1; b < n; b++) { for (int c = b+1; c < n; c++) { if (colinear(p[a],p[b],p[c])) { if (((p[b]-p[a])|(p[c]-p[a])) < 0) include[a] = false; else if (((p[a]-p[b])|(p[c]-p[b])) < 0) include[b] = false; else include[c] = false; } } } } int next_free = 0; for (int i = 0; i < n; ++i) { if (include[i]) { p[next_free] = p[i]; next_free += 1; } } n = next_free; p.resize(n); // To find the faces, we iterate over all triples of non-colinear points // a,b,c and consider the plane spanned by these three points. i64 volume = 0; unordered_set seen_hashes; for (int a = 0; a < n; a++) { for (int b = a+1; b < n; b++) { for (int c = b+1; c < n; c++) { if (colinear(p[a],p[b],p[c])) { continue; } // We gather all points that are coplanar to a,b,c and record // whether there are points to either side of the plane based // on the signed volume. bool found_positive = false; bool found_negative = false; vector face; point inside; for (int d = 0; d < n; d++) { if (d == a || d == b || d == c) { face.push_back(d); continue; } i64 side = orient(p[a],p[b],p[c],p[d]); if (side == 0) { face.push_back(d); } else { inside = p[d]; if (side > 0) found_positive = true; else found_negative = true; } } // If there are points on both sides of the plane it is not a face. if (found_positive && found_negative) continue; // If there are no non-zero values, all points are coplanar and // the volume is therefore 0. if (!found_positive && !found_negative) return 0; // Don't process the same face more than once. We identify each // face by hashing the smallest three indices found in the face. // Since at least a, b and c, this is always possible. int face_hash = face[0] + n * (face[1] + n * face[2]); if (seen_hashes.count(face_hash)) continue; seen_hashes.insert(face_hash); // Now it is guaranteed that the plane abc contains a face // of the polyhedron and that `inside` is on the same side // of the plane as the rest of the polyhedron. // Next, we need to find the actual face, i.e. the 2D convex // hull of the points in the plane. // We project all points onto the axis given by vector ab // and pick one of the extremal points (here: minimum). // This point is guaranteed to be part of the convex hull. point dir = p[b]-p[a]; auto it = min_element(begin(face), end(face), [&](int i, int j) { return (p[i]|dir) < (p[j]|dir); }); swap(face[0],*it); // As with usual convex hull algorithms, we then sort the // points in counterclockwise order around the extremal point. // We can use `orient` for this. auto turn = [&](int i, int j, int k) { return orient(inside,p[i],p[j],p[k]); }; auto comp = [&](int i, int j) { i64 t = turn(face[0],i,j); if (t != 0) return t > 0; return dist2(p[face[0]], p[i]) < dist2(p[face[0]], p[j]); }; sort(next(begin(face)), end(face), comp); // Now run the usual Graham scan on the sorted list. int k = 2; for (int i = 2; i < int(face.size()); i++) { face[k++] = face[i]; while (k >= 3 && turn(face[k-3],face[k-2],face[k-1]) <= 0) { face[k-2] = face[k-1], k--; } } face.resize(k); // Finally, triangulate the face and add up its contribution to // the total volume. for (int i = 1; i+1 < k; i++) { volume += orient(zero, p[face[0]], p[face[i]], p[face[i+1]]); } } } } return volume; } const int MAX_N = 100; int main(int argc, char **argv) { init_io(argc,argv); i64 a, b, c, target_volume; judge_in >> a >> b >> c >> target_volume; int n; if (!(author_out >> n)) { wrong_answer("Wrong answer: expected an integer, the number of points.\n"); } if (n < 4 || n > MAX_N) { wrong_answer("Wrong answer: number of points out of bounds, " "must be between 4 and %d inclusive.\n", MAX_N); } vector p(n); for (int i = 0; i < n; i++) { int x, y, z; if (!(author_out >> x >> y >> z)) { wrong_answer("Wrong answer: expected three integers, the coordinates " "of point %d.\n", i+1); } if (x < 0 || x > a || y < 0 || y > b || z < 0 || z > c) { wrong_answer("Wrong answer: coordinates of point %d out of bounds.\n", i+1); } p[i] = {x,y,z}; } i64 volume = convex_hull(p); if (volume != target_volume) { wrong_answer("Wrong answer: the volume of the polyhedron is %lld (/6), " "but should be %lld (/6).\n", volume, target_volume); } string junk; if (author_out >> junk) { wrong_answer("Wrong answer: found trailing output.\n"); } accept(); }