Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <queue>
- #include <set>
- #include <algorithm>
- using namespace std;
- class ConvexHull {
- public:
- explicit ConvexHull(size_t num) {
- dots.clear();
- num_dots = num;
- }
- ~ConvexHull() {
- dots.clear();
- }
- void read_dots(){
- for(int i = 0; i < num_dots; i++) {
- double x = 0;
- double y = 0;
- double z = 0;
- cin >> x >> y >> z;
- Point tmp(x, y, z);
- tmp.num = i;
- dots.push_back(tmp);
- }
- }
- void print_convex() {
- set<Flat>ans;
- Point First = dots[0];
- Point Second = dots[1];
- Point Third = dots[2];
- Initilize(First,Second, Third);
- queue<Flat> faces;
- Point vertical = CrossProduct(Point(First, Second), Point(First, Third));
- Point normal = CrossProduct(Point(First, Second), Point(First, Third));
- Point tmp_point;
- if (First.num != 0 && Second.num != 0 && Third.num != 0) {
- tmp_point = dots[0];
- } else if (First.num != 1 && Second.num != 1 &&
- Third.num != 1) {
- tmp_point = dots[1];
- } else if (First.num != 2 && Second.num != 2 &&
- Third.num != 2) {
- tmp_point = dots[2];
- } else {
- tmp_point = dots[3];
- }
- if (Scalar(normal, Point(First, tmp_point)) > 0) {
- normal.x *= -1;
- normal.y *= -1;
- normal.z *= -1;
- }
- if (vertical.x * normal.x <= 0 && vertical.y * normal.y <= 0 && vertical.z * normal.z <= 0) {
- Point tmp = Second;
- Second = Third;
- Third = tmp;
- }
- Flat FirstFace = Flat(First, Second, Third,dots);
- faces.push(FirstFace);
- ans.insert(FirstFace);
- while(!faces.empty()) {
- Flat face = faces.front();
- Point n = face.Normal(dots);
- double first_angle = -1*M_PI;
- double second_angle = -1*M_PI;
- double third_angle = -1*M_PI;
- Flat first_flat;
- Flat second_flat;
- Flat third_flat;
- for (int i = 0 ; i < dots.size(); ++i) {
- if (face.First.num != i && face.Second.num != i && face.Third.num != i) {
- Flat f1_test = Flat(face.First, dots[i], face.Second, dots);
- Flat f2_test = Flat(face.Second, dots[i], face.Third, dots);
- Flat f3_test = Flat(face.Third, dots[i], face.First, dots);
- Point n1 = CrossProduct(Point(f1_test.First,f1_test.Second),Point(f1_test.First,f1_test.Third));
- Point n2 = CrossProduct(Point(f2_test.First,f2_test.Second),Point(f2_test.First,f2_test.Third));
- Point n3 = CrossProduct(Point(f3_test.First,f3_test.Second),Point(f3_test.First,f3_test.Third));
- double new_g1 = Scalar(n, n1) / n.Mod() / n1.Mod();
- double new_g2 = Scalar(n, n2) / n.Mod() / n2.Mod();
- double new_g3 = Scalar(n, n3) / n.Mod() / n3.Mod();
- if (new_g1 > first_angle) {
- first_angle = new_g1;
- first_flat = f1_test;
- }
- if (new_g2 > second_angle) {
- second_angle = new_g2;
- second_flat = f2_test;
- }
- if (new_g3 > third_angle) {
- third_angle = new_g3;
- third_flat = f3_test;
- }
- }
- }
- bool b1 = true, b2 = true, b3 = true;
- if (ans.count(first_flat) != 0){b1 = false;}
- if (ans.count(second_flat) != 0){b2 = false;}
- if (ans.count(third_flat) != 0){b3 = false;}
- if (first_flat == second_flat) {b1 = false;}
- if (first_flat == third_flat) {b2 = false;}
- if (second_flat == third_flat) {b3 = false;}
- if (b1) {
- faces.push(first_flat);
- ans.insert(first_flat);
- }
- if (b2) {
- faces.push(second_flat);
- ans.insert(second_flat);
- }
- if (b3) {
- faces.push(third_flat);
- ans.insert(third_flat);
- }
- faces.pop();
- }
- cout << ans.size() << endl;
- for (Flat face: ans) {
- cout << 3 << ' ' << face.First.num << ' ' << face.Second.num << ' ' << face.Third.num << endl;
- }
- }
- private:
- struct Point{
- double x; // Координата точки по x
- double y; // Координата точки по y
- double z; // Координата точки по z
- int num; // Номер точки
- double Mod(){
- return sqrt(x*x+y*y+z*z);
- }
- Point() : x(0), y(0), z(0) {}
- Point(Point A, Point B) : x(B.x-A.x), y(B.y-A.y), z(B.z-A.z), num(-1) {}
- Point(double X, double Y, double Z) : x(X), y(Y), z(Z), num(-1) {}
- };
- Point static CrossProduct (const Point& A,const Point& B) {
- return Point{
- .x = A.y*B.z-A.z*B.y,
- .y = A.z*B.x-A.x*B.z,
- .z = A.x*B.y-A.y*B.x,
- };
- }
- double static Scalar(const Point& A,const Point& B) {
- return(A.x*B.x+A.y*B.y+A.z*B.z);
- }
- double FindAngleBetweenPlanes(Point F1, Point F2,Point F3, Point S1, Point S2,Point S3)
- {
- Point normalF = CrossProduct(Point(F1, F2), Point(F1, F3));
- Point normalS = CrossProduct(Point(S1, S2), Point(S1, S3));
- return Scalar(normalF, normalS) / normalF.Mod() / normalS.Mod();
- }
- vector<Point> dots;
- size_t num_dots;
- struct Flat {
- Point First;
- Point Second;
- Point Third;
- Flat() : First(), Second(), Third() {}
- Flat(Point F, Point S, Point T, vector<Point> dots) : First(F), Second(S), Third(T) {
- while (Second.num < First.num || Third.num < First.num) {
- Point tmp = First;
- First = Second;
- Second = Third;
- Third = tmp;
- }
- }
- Point Normal(vector<Point> dots) {
- Point n = CrossProduct(Point(First, Second), Point(First, Third));
- int someDot;
- for (int i = 0; i < 4; ++i) {
- if (First.num == i) {continue;}
- if (Second.num == i) {continue;}
- if (Third.num == i) {continue;}
- someDot = i;
- break;
- }
- if (Scalar(n, Point(First, dots[someDot])) > 0) {
- n.x = - n.x;
- n.y = - n.y;
- n.z = - n.z;
- }
- return n;
- }
- bool operator<(const Flat& other) const
- {
- return (First.num < other.First.num || (First.num == other.First.num && (Second.num < other.Second.num ||
- Second.num == other.Second.num && Third.num < other.Third.num))) ? true : false;
- }
- bool operator==(const Flat& other) const
- {
- return (First.num == other.First.num & Second.num == other.Second.num && Third.num == other.Third.num) ? true : false;
- }
- };
- void Initilize(Point& First, Point& Second, Point& Third) {
- for (int i = 0; i < num_dots; i++) { // Находим эту самую точку first_point
- if (dots[i].z < First.z) {
- First = dots[i];
- } else if (dots[i].z == First.z) {
- if (dots[i].x < First.x) {
- First = dots[i];
- } else if (dots[i].x == First.x) {
- if (dots[i].y < First.y) {
- First = dots[i];
- }
- }
- }
- }
- double max_angle = -1;
- // В качестве l возьмем прямую проходящую через first_point и какую-то случайную точку
- Point l_point(rand() % 100 + 1985, rand() % 30 + 1985, First.z);
- for (int i = 0; i < dots.size(); ++i) {
- if (i != First.num) {
- double angle = FindAngleBetweenPlanes(First, l_point, Point(-1*First.x,-1*Second.x,-1*Third.x), First, l_point, dots[i]);
- if (angle >= max_angle) {
- max_angle = angle;
- Second = dots[i];
- }
- }
- }
- max_angle = -1;
- for (int i = 0; i < dots.size(); ++i) {
- if (i != First.num && i != Second.num) {
- double angle = FindAngleBetweenPlanes(First, l_point, Second, First, Second, dots[i]);
- if (angle >= max_angle) {
- max_angle = angle;
- Third = dots[i];
- }
- }
- }
- }
- };
- int main() {
- int num_tests = 0;
- cin >> num_tests;
- for(int test = 0; test < num_tests; test++){
- size_t num_dots = 0;
- cin >> num_dots;
- ConvexHull convex(num_dots);
- convex.read_dots();
- convex.print_convex();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement