Advertisement
faunuss

new_unstable

Nov 27th, 2017
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.36 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <queue>
  5. #include <set>
  6. #include <algorithm>
  7. using namespace std;
  8.  
  9. class ConvexHull {
  10. public:
  11.     explicit ConvexHull(size_t num) {
  12.         dots.clear();
  13.         num_dots = num;
  14.     }
  15.     ~ConvexHull() {
  16.         dots.clear();
  17.     }
  18.     void read_dots(){
  19.         for(int i = 0; i < num_dots; i++) {
  20.             double x = 0;
  21.             double y = 0;
  22.             double z = 0;
  23.             cin >> x >> y >> z;
  24.             Point tmp(x, y, z);
  25.             tmp.num = i;
  26.             dots.push_back(tmp);
  27.         }
  28.     }
  29.     void print_convex() {
  30.         set<Flat>ans;
  31.  
  32.         Point First = dots[0];
  33.         Point Second = dots[1];
  34.         Point Third = dots[2];
  35.  
  36.         Initilize(First,Second, Third);
  37.  
  38.         queue<Flat> faces;
  39.  
  40.         Point vertical = CrossProduct(Point(First, Second), Point(First, Third));
  41.         Point normal = CrossProduct(Point(First, Second), Point(First, Third));
  42.         Point tmp_point;
  43.  
  44.         if (First.num != 0 && Second.num != 0 && Third.num != 0) {
  45.             tmp_point = dots[0];
  46.         } else if (First.num != 1 && Second.num != 1 &&
  47.                    Third.num != 1) {
  48.             tmp_point = dots[1];
  49.         } else if (First.num != 2 && Second.num != 2 &&
  50.                    Third.num != 2) {
  51.             tmp_point = dots[2];
  52.         } else {
  53.             tmp_point = dots[3];
  54.         }
  55.  
  56.         if (Scalar(normal, Point(First, tmp_point)) > 0) {
  57.             normal.x *= -1;
  58.             normal.y *= -1;
  59.             normal.z *= -1;
  60.         }
  61.  
  62.         if (vertical.x * normal.x <= 0 && vertical.y * normal.y <= 0 && vertical.z * normal.z <= 0) {
  63.             Point tmp = Second;
  64.             Second = Third;
  65.             Third = tmp;
  66.         }
  67.  
  68.         Flat FirstFace = Flat(First, Second, Third,dots);
  69.  
  70.         faces.push(FirstFace);
  71.         ans.insert(FirstFace);
  72.  
  73.         while(!faces.empty()) {
  74.             Flat face = faces.front();
  75.             Point n = face.Normal(dots);
  76.             double first_angle = -1*M_PI;
  77.             double second_angle = -1*M_PI;
  78.             double third_angle = -1*M_PI;
  79.             Flat first_flat;
  80.             Flat second_flat;
  81.             Flat third_flat;
  82.             for (int i = 0 ; i < dots.size(); ++i) {
  83.                 if (face.First.num != i && face.Second.num != i && face.Third.num != i) {
  84.                     Flat f1_test = Flat(face.First, dots[i], face.Second, dots);
  85.                     Flat f2_test = Flat(face.Second, dots[i], face.Third, dots);
  86.                     Flat f3_test = Flat(face.Third, dots[i], face.First, dots);
  87.                     Point n1 = CrossProduct(Point(f1_test.First,f1_test.Second),Point(f1_test.First,f1_test.Third));
  88.                     Point n2 = CrossProduct(Point(f2_test.First,f2_test.Second),Point(f2_test.First,f2_test.Third));
  89.                     Point n3 = CrossProduct(Point(f3_test.First,f3_test.Second),Point(f3_test.First,f3_test.Third));
  90.                     double new_g1 = Scalar(n, n1) / n.Mod() / n1.Mod();
  91.                     double new_g2 = Scalar(n, n2) / n.Mod() / n2.Mod();
  92.                     double new_g3 = Scalar(n, n3) / n.Mod() / n3.Mod();
  93.                     if (new_g1 > first_angle) {
  94.                         first_angle = new_g1;
  95.                         first_flat = f1_test;
  96.                     }
  97.                     if (new_g2 > second_angle) {
  98.                         second_angle = new_g2;
  99.                         second_flat = f2_test;
  100.                     }
  101.                     if (new_g3 > third_angle) {
  102.                         third_angle = new_g3;
  103.                         third_flat = f3_test;
  104.                     }
  105.                 }
  106.             }
  107.             bool b1 = true, b2 = true, b3 = true;
  108.             if (ans.count(first_flat) != 0){b1 = false;}
  109.             if (ans.count(second_flat) != 0){b2 = false;}
  110.             if (ans.count(third_flat) != 0){b3 = false;}
  111.             if (first_flat == second_flat) {b1 = false;}
  112.             if (first_flat == third_flat) {b2 = false;}
  113.             if (second_flat == third_flat) {b3 = false;}
  114.             if (b1) {
  115.                 faces.push(first_flat);
  116.                 ans.insert(first_flat);
  117.             }
  118.             if (b2) {
  119.                 faces.push(second_flat);
  120.                 ans.insert(second_flat);
  121.             }
  122.             if (b3) {
  123.                 faces.push(third_flat);
  124.                 ans.insert(third_flat);
  125.             }
  126.             faces.pop();
  127.         }
  128.         cout << ans.size() << endl;
  129.         for (Flat face: ans) {
  130.             cout << 3 << ' ' << face.First.num << ' ' << face.Second.num << ' ' << face.Third.num << endl;
  131.         }
  132.     }
  133. private:
  134.     struct Point{
  135.         double x;   // Координата точки по x
  136.         double y;   // Координата точки по y
  137.         double z;   // Координата точки по z
  138.         int num;    // Номер точки
  139.  
  140.         double Mod(){
  141.             return sqrt(x*x+y*y+z*z);
  142.         }
  143.         Point() : x(0), y(0), z(0) {}
  144.         Point(Point A, Point B) : x(B.x-A.x), y(B.y-A.y), z(B.z-A.z), num(-1) {}
  145.         Point(double X, double Y, double Z) : x(X), y(Y), z(Z), num(-1) {}
  146.     };
  147.     Point static CrossProduct (const Point& A,const Point& B) {
  148.         return Point{
  149.                 .x = A.y*B.z-A.z*B.y,
  150.                 .y = A.z*B.x-A.x*B.z,
  151.                 .z = A.x*B.y-A.y*B.x,
  152.                 };
  153.     }
  154.     double static Scalar(const Point& A,const Point& B) {
  155.         return(A.x*B.x+A.y*B.y+A.z*B.z);
  156.     }
  157.  
  158.     double FindAngleBetweenPlanes(Point F1, Point F2,Point F3, Point S1, Point S2,Point S3)
  159.     {
  160.         Point normalF = CrossProduct(Point(F1, F2), Point(F1, F3));
  161.         Point normalS = CrossProduct(Point(S1, S2), Point(S1, S3));
  162.         return Scalar(normalF, normalS) / normalF.Mod() / normalS.Mod();
  163.     }
  164.  
  165.     vector<Point> dots;
  166.     size_t num_dots;
  167.  
  168.     struct Flat {
  169.         Point First;
  170.         Point Second;
  171.         Point Third;
  172.         Flat() : First(), Second(), Third() {}
  173.         Flat(Point F, Point S, Point T, vector<Point> dots) : First(F), Second(S), Third(T) {
  174.             while (Second.num < First.num || Third.num < First.num) {
  175.                 Point tmp = First;
  176.                 First = Second;
  177.                 Second = Third;
  178.                 Third = tmp;
  179.             }
  180.         }
  181.         Point Normal(vector<Point> dots) {
  182.             Point n = CrossProduct(Point(First, Second), Point(First, Third));
  183.             int someDot;
  184.             for (int i = 0; i < 4; ++i) {
  185.                 if (First.num == i) {continue;}
  186.                 if (Second.num == i) {continue;}
  187.                 if (Third.num == i) {continue;}
  188.                 someDot = i;
  189.                 break;
  190.             }
  191.             if (Scalar(n, Point(First, dots[someDot])) > 0) {
  192.                 n.x = - n.x;
  193.                 n.y = - n.y;
  194.                 n.z = - n.z;
  195.             }
  196.             return n;
  197.         }
  198.  
  199.         bool operator<(const Flat& other) const
  200.         {
  201.             return (First.num < other.First.num || (First.num == other.First.num && (Second.num < other.Second.num ||
  202.                                                      Second.num == other.Second.num && Third.num < other.Third.num))) ? true : false;
  203.         }
  204.  
  205.         bool operator==(const Flat& other) const
  206.         {
  207.             return (First.num == other.First.num & Second.num == other.Second.num && Third.num == other.Third.num) ? true : false;
  208.         }
  209.     };
  210.  
  211.     void Initilize(Point& First, Point& Second, Point& Third) {
  212.         for (int i = 0; i < num_dots; i++) {  // Находим эту самую точку first_point
  213.             if (dots[i].z < First.z) {
  214.                 First = dots[i];
  215.             } else if (dots[i].z == First.z) {
  216.                 if (dots[i].x < First.x) {
  217.                     First = dots[i];
  218.                 } else if (dots[i].x == First.x) {
  219.                     if (dots[i].y < First.y) {
  220.                         First = dots[i];
  221.                     }
  222.                 }
  223.             }
  224.         }
  225.  
  226.         double max_angle = -1;
  227.         // В качестве l возьмем  прямую проходящую через first_point и какую-то случайную точку
  228.         Point l_point(rand() % 100 + 1985, rand() % 30 + 1985, First.z);
  229.         for (int i = 0; i < dots.size(); ++i) {
  230.             if (i != First.num) {
  231.                 double angle = FindAngleBetweenPlanes(First, l_point, Point(-1*First.x,-1*Second.x,-1*Third.x),  First, l_point, dots[i]);
  232.                     if (angle >= max_angle) {
  233.                         max_angle = angle;
  234.                         Second = dots[i];
  235.                     }
  236.                 }
  237.             }
  238.  
  239.         max_angle = -1;
  240.         for (int i = 0; i < dots.size(); ++i) {
  241.             if (i != First.num && i != Second.num) {
  242.                 double angle = FindAngleBetweenPlanes(First, l_point, Second, First, Second, dots[i]);
  243.                 if (angle >= max_angle) {
  244.                     max_angle = angle;
  245.                     Third = dots[i];
  246.                 }
  247.             }
  248.         }
  249.     }
  250. };
  251.  
  252. int main() {
  253.     int num_tests = 0;
  254.     cin >> num_tests;
  255.  
  256.     for(int test = 0; test < num_tests; test++){
  257.         size_t num_dots = 0;
  258.         cin >> num_dots;
  259.  
  260.         ConvexHull convex(num_dots);
  261.         convex.read_dots();
  262.         convex.print_convex();
  263.     }
  264. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement