Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <algorithm>
- #include <iomanip>
- #include <cassert>
- using namespace std;
- typedef long double ld;
- #define Vec Point
- #define Vec3d Point3d
- const ld EPS = 1e-9;
- int sign(ld x) {
- if (x > EPS) { return 1; }
- if (x < -EPS) { return -1; }
- return 0;
- }
- ld sq(ld x) {
- return x * x;
- }
- struct Point {
- ld x, y, z;
- Point() : x(0), y(0), z(0) {}
- Point(ld _x, ld _y, ld _z) : x(_x), y(_y), z(_z) {}
- Point operator-(const Point& other) const {
- return Point(x - other.x, y - other.y, z - other.z);
- }
- Point operator+(const Point& other) const {
- return Point(x + other.x, y + other.y, z + other.z);
- }
- Point operator*(const ld& other) const {
- return Point(x * other, y * other, z * other);
- }
- ld operator^(const Point& other) const {
- return x * other.y - y * other.x;
- }
- ld operator*(const Point& other) const {
- return x * other.x + y * other.y + z * other.z;
- }
- ld len2() const {
- return sq(x) + sq(y) + sq(z);
- }
- ld len() const {
- return sqrtl(len2());
- }
- Point norm() const {
- ld d = len();
- return Point(x / d, y / d, z / d);
- }
- bool operator<(const Point& other) const {
- if (sign(x - other.x) != 0) {
- return x < other.x;
- }
- else if (sign(y - other.y) != 0) {
- return y < other.y;
- }
- return false;
- }
- bool operator==(const Point& other) const {
- return sign(x - other.x) == 0 && sign(y - other.y) == 0 && sign(z - other.z) == 0;
- }
- };
- bool cmp(const Point& a, const Point& b) {
- if (sign(a ^ b)) {
- return sign(a ^ b) == 1;
- }
- else {
- return sign(b.len2() - a.len2()) == 1;
- }
- }
- vector<Point> Erase_same_points(vector<Point>& p) {
- if (p.empty())return {};
- int pos = min_element(p.begin(), p.end()) - p.begin();
- swap(p[0], p[pos]);
- for (int i = 1; i < (int)p.size(); i++) {
- p[i] = p[i] - p[0];
- }
- stable_sort(p.begin() + 1, p.end(), cmp);
- for (int i = 1; i < (int)p.size(); i++) {
- p[i] = p[i] + p[0];
- }
- p.resize(unique(p.begin(), p.end()) - p.begin());
- return p;
- }
- ld get_S(vector<Point>& p) {
- int n = (int)p.size();
- ld ans = 0;
- for (int i = 0; i < n; i++) {
- ans += p[i] ^ p[i + 1 < n ? i + 1 : 0];
- }
- return fabs((ld)ans / 2);
- }
- bool intersect_plane_segment(Point segA, Point segB, Vec plane_norm, Point plane_point, Point& res_point) {
- Vec ray = segB - segA;
- if (sign(plane_norm * ray) == 0) {
- return false;
- }
- //(plane_point - segA + ray * t) * plane_norm = 0
- //
- ld t = (plane_point * plane_norm - segA * plane_norm) / (ray * plane_norm);
- res_point = segA + ray * t;
- if (t > -EPS && t < 1 + EPS) {
- return true;
- }
- return false;
- }
- ld get_S(vector<vector<Point>>& poly3d, ld z) {
- Vec up(0., 0., 1.);
- Vec plane_point(10., 10., z);
- vector<Point> inter;
- for (int i = 0; i < poly3d.size(); i++) {
- for (int j = 0; j < poly3d[i].size(); j++) {
- Point res = Point();
- if (intersect_plane_segment(poly3d[i][j], poly3d[i][j + 1 < poly3d[i].size() ? j + 1 : 0], up, plane_point, res)) {
- inter.push_back(res);
- }
- }
- }
- vector<Point> hull = Erase_same_points(inter);
- return get_S(hull);
- }
- int main() {
- int n;
- while (cin >> n) {
- if (n == 0) {
- break;
- }
- vector<vector<Point>> Poly3d;
- ld max_z = -1e9, min_z = 1e9;
- for (int i = 0; i < n; i++) {
- int m;
- cin >> m;
- vector<Point> subP;
- for (int j = 0; j < m; j++) {
- Point x;
- cin >> x.x >> x.y >> x.z;
- max_z = max(max_z, x.z);
- min_z = min(min_z, x.z);
- subP.push_back(x);
- }
- Poly3d.push_back(subP);
- }
- ld l = min_z, r = max_z;
- for (int i = 0; i < 200; i++) {
- ld lm = l + (r - l) / 3;
- ld rm = r - (r - l) / 3;
- if (get_S(Poly3d, lm) <= get_S(Poly3d, rm)) {
- l = lm;
- }
- else {
- r = rm;
- }
- }
- cout << fixed << setprecision(8) << get_S(Poly3d, l) << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment