ivnikkk

Untitled

Dec 11th, 2024
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.80 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <iomanip>
  6. #include <cassert>
  7. using namespace std;
  8. typedef long double ld;
  9. #define Vec Point
  10. #define Vec3d Point3d
  11. const ld EPS = 1e-9;
  12.  
  13. int sign(ld x) {
  14.     if (x > EPS) { return 1; }
  15.     if (x < -EPS) { return -1; }
  16.     return 0;
  17. }
  18.  
  19. ld sq(ld x) {
  20.     return x * x;
  21. }
  22.  
  23. struct Point {
  24.     ld x, y, z;
  25.     Point() : x(0), y(0), z(0) {}
  26.     Point(ld _x, ld _y, ld _z) : x(_x), y(_y), z(_z) {}
  27.  
  28.     Point operator-(const Point& other) const {
  29.         return Point(x - other.x, y - other.y, z - other.z);
  30.     }
  31.     Point operator+(const Point& other) const {
  32.         return Point(x + other.x, y + other.y, z + other.z);
  33.     }
  34.     Point operator*(const ld& other) const {
  35.         return Point(x * other, y * other, z * other);
  36.     }
  37.     ld operator^(const Point& other) const {
  38.         return x * other.y - y * other.x;
  39.     }
  40.     ld operator*(const Point& other) const {
  41.         return x * other.x + y * other.y + z * other.z;
  42.     }
  43.     ld len2() const {
  44.         return sq(x) + sq(y) + sq(z);
  45.     }
  46.     ld len() const {
  47.         return sqrtl(len2());
  48.     }
  49.     Point norm() const {
  50.         ld d = len();
  51.         return Point(x / d, y / d, z / d);
  52.     }
  53.  
  54.     bool operator<(const Point& other) const {
  55.         if (sign(x - other.x) != 0) {
  56.             return x < other.x;
  57.         }
  58.         else if (sign(y - other.y) != 0) {
  59.             return y < other.y;
  60.         }
  61.         return false;
  62.     }
  63.     bool operator==(const Point& other) const {
  64.         return sign(x - other.x) == 0 && sign(y - other.y) == 0 && sign(z - other.z) == 0;
  65.     }
  66. };
  67. bool cmp(const Point& a, const Point& b) {
  68.     if (sign(a ^ b)) {
  69.         return sign(a ^ b) == 1;
  70.     }
  71.     else {
  72.         return sign(b.len2() - a.len2()) == 1;
  73.     }
  74. }
  75. vector<Point> Erase_same_points(vector<Point>& p) {
  76.     if (p.empty())return {};
  77.     int pos = min_element(p.begin(), p.end()) - p.begin();
  78.     swap(p[0], p[pos]);
  79.     for (int i = 1; i < (int)p.size(); i++) {
  80.         p[i] = p[i] - p[0];
  81.     }
  82.     stable_sort(p.begin() + 1, p.end(), cmp);
  83.     for (int i = 1; i < (int)p.size(); i++) {
  84.         p[i] = p[i] + p[0];
  85.     }
  86.     p.resize(unique(p.begin(), p.end()) - p.begin());
  87.     return p;
  88. }
  89. ld get_S(vector<Point>& p) {
  90.     int n = (int)p.size();
  91.     ld ans = 0;
  92.     for (int i = 0; i < n; i++) {
  93.         ans += p[i] ^ p[i + 1 < n ? i + 1 : 0];
  94.     }
  95.     return fabs((ld)ans / 2);
  96. }
  97. bool intersect_plane_segment(Point segA, Point segB, Vec plane_norm, Point plane_point, Point& res_point) {
  98.     Vec ray = segB - segA;
  99.     if (sign(plane_norm * ray) == 0) {
  100.         return false;
  101.     }
  102.     //(plane_point - segA + ray * t) * plane_norm = 0
  103.     //
  104.     ld t = (plane_point * plane_norm - segA * plane_norm) / (ray * plane_norm);
  105.     res_point = segA + ray * t;
  106.     if (t > -EPS && t < 1 + EPS) {
  107.         return true;
  108.     }
  109.     return false;
  110.  
  111. }
  112.  
  113. ld get_S(vector<vector<Point>>& poly3d, ld z) {
  114.     Vec up(0., 0., 1.);
  115.     Vec plane_point(10., 10., z);
  116.     vector<Point> inter;
  117.     for (int i = 0; i < poly3d.size(); i++) {
  118.         for (int j = 0; j < poly3d[i].size(); j++) {
  119.             Point res = Point();
  120.             if (intersect_plane_segment(poly3d[i][j], poly3d[i][j + 1 < poly3d[i].size() ? j + 1 : 0], up, plane_point, res)) {
  121.                 inter.push_back(res);
  122.             }
  123.         }
  124.     }
  125.     vector<Point> hull = Erase_same_points(inter);
  126.     return get_S(hull);
  127. }
  128. int main() {
  129.     int n;
  130.     while (cin >> n) {
  131.         if (n == 0) {
  132.             break;
  133.         }
  134.         vector<vector<Point>> Poly3d;
  135.         ld max_z = -1e9, min_z = 1e9;
  136.         for (int i = 0; i < n; i++) {
  137.             int m;
  138.             cin >> m;
  139.             vector<Point> subP;
  140.             for (int j = 0; j < m; j++) {
  141.                 Point x;
  142.                 cin >> x.x >> x.y >> x.z;
  143.                 max_z = max(max_z, x.z);
  144.                 min_z = min(min_z, x.z);
  145.                 subP.push_back(x);
  146.             }
  147.             Poly3d.push_back(subP);
  148.         }
  149.         ld l = min_z, r = max_z;
  150.        
  151.         for (int i = 0; i < 200; i++) {
  152.             ld lm = l + (r - l) / 3;
  153.             ld rm = r - (r - l) / 3;
  154.             if (get_S(Poly3d, lm) <= get_S(Poly3d, rm)) {
  155.                 l = lm;
  156.             }
  157.             else {
  158.                 r = rm;
  159.             }
  160.         }
  161.         cout << fixed << setprecision(8) << get_S(Poly3d, l) << '\n';
  162.     }
  163.     return 0;
  164. }
Advertisement
Add Comment
Please, Sign In to add comment