Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <cmath>
- #include <iostream>
- #include <vector>
- #include <cassert>
- #include <iterator>
- struct Point {
- int x;
- int y;
- int z;
- int number;
- Point(int _x, int _y, int _z, int _number = 0):
- x(_x),
- y(_y),
- z(_z),
- number(_number)
- {
- }
- Point(const Point& other) {
- x = other.x;
- y = other.y;
- z = other.z;
- number = other.number;
- }
- bool operator==(const Point& other) const;
- bool operator!=(const Point& other) const;
- Point operator-(const Point& other) const;
- double operator^(int p) const;
- double operator*(const Point& other) const;
- double GetModule() const;
- void Print() const;
- };
- bool Point::operator==(const Point &other) const{
- return (this->x == other.x && this->y == other.y && this->z == other.z);
- }
- bool Point::operator!=(const Point &other) const{
- return (this->x != other.x || this->y != other.y || this->z != other.z);
- }
- Point Point::operator-(const Point& other) const{
- return {this->x - other.x, this->y - other.y, this->z - other.z};
- }
- double Point::operator^(int p) const{
- return std::pow(this->x,p) + std::pow(this->y,p) + std::pow(this->z,p);
- }
- double Point::operator*(const Point &other) const{
- return (this->x*other.x + this->y*other.y + this->z*other.z);
- }
- Point OtherPointFromSet(const Point& this_point, const std::vector<Point> &points) {
- assert(!points.empty());
- for(const auto& point: points ) {
- if (point != this_point) {
- return point;
- }
- }
- }
- double Point::GetModule() const {
- return std::sqrt( this->x*this->x + this->y*this->y + this->z*this->z );
- }
- void Point::Print() const {
- std::cout<<this->x<<' '<<this->y<<' '<<this->z;
- std::cout<<'\n';
- }
- Point VectorMultiplication(const Point& p1, const Point& p2) {
- return {p1.y*p2.z - p1.z*p2.y, - (p1.x*p2.z - p1.z*p2.x ), p1.x*p2.y - p1.y*p2.x};
- }
- double Distance(const Point& p1, const Point& p2) {
- return std::sqrt( (p1-p2)^2 );
- }
- double OzAngle(const Point& p1, const Point& p2) {
- Point Oz (0,0,1);
- Point p12 = p2 - p1;
- double t = (p12*Oz)/std::sqrt((p12*p12)*(Oz*Oz));
- if (t < -1) {
- t = -1;
- }
- else if(t > 1) {
- t = 1;
- }
- double acos = std::acos(t);
- return acos;
- }
- Point MostBottom(const std::vector<Point>& points) {
- Point point_min = points[0];
- for (const auto& point: points) {
- if (point.z < point_min.z) {
- point_min = point;
- }
- }
- return point_min;
- }
- struct Edge {
- Point p1;
- Point p2;
- Point forbidden_point;
- bool IsProcessed;
- Edge(const Point& _p1, const Point& _p2, const Point& _forbidden_point);
- Edge(const Edge& edge, const Point& _forbidden_point);
- Edge(const Edge& edge);
- Point PivotAroundEdge(const std::vector<Point> &points);
- bool operator==(const Edge& other) const;
- };
- Edge::Edge(const Point& _p1, const Point& _p2, const Point& _forbidden_point) :
- p1(_p1),
- p2(_p2),
- forbidden_point(_forbidden_point),
- IsProcessed(false)
- {
- }
- Edge::Edge(const Edge& edge, const Point& _forbidden_point) :
- p1(edge.p1),
- p2(edge.p2),
- forbidden_point(_forbidden_point),
- IsProcessed(false)
- {
- }
- Edge::Edge(const Edge &edge) :
- p1(edge.p1),
- p2(edge.p2),
- forbidden_point(edge.forbidden_point),
- IsProcessed(edge.IsProcessed)
- {
- }
- bool Edge::operator==(const Edge& other) const{
- return (this->p1 == other.p1 && this->p2 == other.p2 ||
- this->p1 == other.p2 && this->p2 == other.p1);
- }
- double FindOutFaceD(double A, double B, double C, const Point& pivot) {
- return -( A*pivot.x + B*pivot.y + C*pivot.z );
- }
- struct Triangle {
- Edge edge12;
- Edge edge23;
- Edge edge31;
- Triangle(const Edge& edge, const Point& point);
- Triangle(const Edge& edge1, const Edge& edge2, const Edge& edge3);
- std::vector<Edge> GetEdges();
- Point GetExternalVector(const std::vector<Point>& points);
- std::vector<Point> GetPointsInProperOrder(const std::vector<Point> &points);
- };
- Triangle::Triangle(const Edge& edge, const Point& point) :
- edge12(edge, point),
- edge23(edge.p1, point, edge.p2),
- edge31(edge.p2, point, edge.p1)
- {
- }
- Triangle::Triangle(const Edge& edge1, const Edge& edge2, const Edge& edge3) :
- edge12(edge1),
- edge23(edge2),
- edge31(edge3)
- {
- }
- Point GetOtherPoint(const std::vector<Point>& triangles_points, const std::vector<Point> &points) {
- assert(triangles_points.size() == 3);
- for (const auto& point: points) {
- if ((point != triangles_points[1] && point != triangles_points[2])
- && point != triangles_points[0]) {
- return point;
- }
- }
- }
- std::vector<Point> GetPointsOfTriangle(const Triangle& triangle) {
- std::vector<Point> points = { triangle.edge12.p1, triangle.edge12.p2, triangle.edge23.p1,
- triangle.edge23.p2, triangle.edge31.p1, triangle.edge31.p2 };
- std::sort(points.begin(), points.end(), [](const Point& p1, const Point& p2){ return p1.number <= p2.number ; });
- auto last = std::unique(points.begin(), points.end());
- points.erase(last, points.end());
- return points;
- }
- Point Triangle::GetExternalVector(const std::vector<Point>& points) { //O(1)
- Triangle this_triangle = *this;
- std::vector<Point> triangles_points = GetPointsOfTriangle(this_triangle);
- assert(triangles_points.size() == 3);
- Point v1 = triangles_points[1] - triangles_points[0];
- Point v2 = triangles_points[2] - triangles_points[0];
- Point vector_normal_1 = VectorMultiplication(v1,v2);
- Point vector_normal_2 = VectorMultiplication(v2,v1);
- double D_1 = FindOutFaceD(vector_normal_1.x, vector_normal_1.y, vector_normal_1.z, triangles_points[0]);
- double D_2 = FindOutFaceD(vector_normal_2.x, vector_normal_2.y, vector_normal_2.z, triangles_points[0]);
- Point other_point = GetOtherPoint(triangles_points, points);
- if (vector_normal_1*other_point + D_1 < 0) {
- return vector_normal_1;
- }
- else if (vector_normal_2*other_point + D_2 < 0) {
- return vector_normal_2;
- }
- else {
- std::cout<<"Can't Find External Vector for Triangle";
- exit(1);
- }
- }
- std::vector<Point> Triangle::GetPointsInProperOrder(const std::vector<Point> &points) {
- Triangle this_triangle = *this;
- std::vector<Point> triangle_points = GetPointsOfTriangle(this_triangle);
- std::vector<Point> proper_order_points;
- Point external_normal_vector = this->GetExternalVector(points);
- int iter_of_min = 0; //FIX!!!
- for (int i = 1; i < triangle_points.size(); ++i) {
- if (triangle_points[iter_of_min].number > triangle_points[i].number) {
- iter_of_min = i;
- }
- }
- std::swap(triangle_points[iter_of_min],triangle_points[0]);
- proper_order_points.push_back(triangle_points[0]);
- Point v1 = VectorMultiplication(triangle_points[1] - triangle_points[0],external_normal_vector);
- Point v2 = VectorMultiplication(triangle_points[2] - triangle_points[0],external_normal_vector);
- double D_1 = FindOutFaceD(v1.x , v1.y, v1.z, triangle_points[1]);
- double D_2 = FindOutFaceD(v2.x , v2.y, v2.z, triangle_points[2]);
- if ( v1*triangle_points[2] + D_1 < 0 ) {
- proper_order_points.push_back(triangle_points[1]);
- proper_order_points.push_back(triangle_points[2]);
- }
- else if ( v2*triangle_points[1] + D_2 < 0 ) {
- proper_order_points.push_back(triangle_points[2]);
- proper_order_points.push_back(triangle_points[1]);
- }
- else {
- std::cout<<"Can't find right order";
- exit(1);
- }
- return proper_order_points;
- }
- std::vector<Edge> Triangle::GetEdges() {
- return {edge12,edge23,edge31};
- }
- double AngleBetweenTriangles(const std::vector<Point>& points, Triangle& first, Triangle& second) {
- Point v1 = first.GetExternalVector(points);
- Point v2 = second.GetExternalVector(points);
- double angle = (v1 * v2)/(v1.GetModule() * v2.GetModule());
- return angle;
- }
- bool IsFace(Triangle& triangle, const std::vector<Point>& points) { // how to do O(1)
- std::vector<Point> triangles_points = GetPointsOfTriangle(triangle);
- Point normal = triangle.GetExternalVector(points);
- double D_of_triangle = FindOutFaceD(normal.x, normal.y, normal.z, triangles_points[0]);
- std::vector<double> D_of_other_points;
- for (const auto& point: points) {
- if ( (point != triangles_points[1] && point != triangles_points[2]) && point != triangles_points[0]) {
- double D = FindOutFaceD(normal.x, normal.y, normal.z, point);
- D_of_other_points.push_back(D);
- }
- }
- double min_element = *std::min_element(D_of_other_points.begin(), D_of_other_points.end());
- double max_element = *std::max_element(D_of_other_points.begin(), D_of_other_points.end());
- bool result = (D_of_triangle < min_element ||
- D_of_triangle > max_element ) ;
- return result;
- }
- Edge FindEdgeOnHull(const std::vector<Point>& points) {
- Point p1 = MostBottom(points);
- Point p2 = OtherPointFromSet(p1, points);
- for (const auto& point: points) {
- if ( p1 != point && OzAngle(p1,point) >= OzAngle(p1,p2) ) {
- p2 = point;
- }
- }
- return {p1,p2,p1};
- }
- Triangle FindtTriangleOnHull(std::vector<Point>& points) { //O(n^2)
- Edge edge = FindEdgeOnHull(points);
- Point pivot = edge.PivotAroundEdge(points);
- edge.forbidden_point = pivot;
- return {edge, pivot};
- }
- Triangle FindNewTriangle(const std::vector<Point> &points, const Edge& edge) { // need O(n)
- Point p1 = edge.p1;
- Point p2 = edge.p2;
- Point forbidden_point = edge.forbidden_point;
- Triangle based_triangle = Triangle(edge, forbidden_point);
- std::vector<Point> triangle_points = GetPointsOfTriangle(based_triangle);
- Point other_point = GetOtherPoint(triangle_points, points);
- Triangle current_triangle = Triangle(edge, other_point); //!!
- for (const auto& point: points) { // need O(n)
- if ((point != p1 && point != p2) && point != forbidden_point) {
- Triangle new_triangle (edge, point);
- if (AngleBetweenTriangles(points, based_triangle, new_triangle) >
- AngleBetweenTriangles(points, based_triangle, current_triangle)) { // O(1)
- current_triangle = new_triangle;
- }
- }
- }
- return current_triangle;
- }
- Point Edge::PivotAroundEdge(const std::vector<Point> &points) { // O(n^2)
- Point p1 = this->p1;
- Point p2 = this->p2;
- for (const auto& point: points) {
- if ((point != p1 && point != p2)) {
- Edge this_edge = *this;
- Triangle triangle (this_edge, point);
- if (IsFace(triangle, points)) { // O(n)
- return point;
- }
- }
- }
- }
- bool IsNotUsedEdges(const std::vector<Edge>& edges) {
- bool result = true;
- for (auto edge: edges) {
- result = result && edge.IsProcessed;
- }
- return !result;
- }
- template <class T>
- bool IsIn(const T& myelement, std::vector<T>& elements) {
- for (int i = 0; i < elements.size(); ++i) {
- if (myelement == elements[i]) {
- elements[i].IsProcessed = true;
- return true;
- }
- }
- return false;
- }
- void GiftWrapping(std::vector<Point>& points, std::vector<Triangle> & faces) {
- Triangle t = FindtTriangleOnHull(points); // O(n^2)
- faces.push_back(t);
- std::vector<Edge> edges = t.GetEdges();
- while (IsNotUsedEdges(edges)) { // O(n)
- Edge &newedge = edges.back();
- if (!newedge.IsProcessed) {
- newedge.IsProcessed = true;
- Triangle newtriangle = FindNewTriangle(points, newedge); //O(n) //
- std::vector<Edge> triangles_edges = newtriangle.GetEdges();
- for (const auto& edge: triangles_edges) {
- if (!IsIn(edge, edges)) {
- edges.push_back(edge);
- }
- }
- faces.push_back(newtriangle);
- }
- }
- }
- void SortByDigit(std::vector<std::vector<int>>& vector, int digit_number) {
- std::sort(vector.begin(), vector.end(),
- [digit_number](const std::vector<int>& a, const std::vector<int>&b) {
- return a[digit_number] < b[digit_number];
- });
- }
- void Start() {
- int m; // число тестов
- std::cin>>m;
- for (int i = 0; i < m; ++i) {
- int n; // число точек
- std::cin>>n;
- std::vector<Point> points;
- std::vector<Triangle> faces;
- for (int j = 0; j < n; ++j) {
- int x,y,z;
- std::cin>>x>>y>>z;
- points.emplace_back(Point(x,y,z,j));
- }
- GiftWrapping(points, faces);
- std::cout<<faces.size()<<std::endl;
- std::vector<std::vector<int>> lexic_order(faces.size());
- for (int k = 0; k < faces.size(); ++k) {
- lexic_order[k].push_back(3);
- for (auto point: faces[k].GetPointsInProperOrder(points)) {
- lexic_order[k].push_back(point.number);
- }
- }
- // sort
- for (int t = lexic_order[0].size() - 1; t > 0 ; --t) {
- SortByDigit(lexic_order, t);
- }
- // output
- for (const auto& face: lexic_order) {
- for (const auto& number: face) {
- std::cout<<number<<' ';
- }
- std::cout<<'\n';
- }
- }
- }
- bool predicate(const Point& p1, const Point& p2) {
- return (p1 == p2);
- }
- int main() {
- // Point p1 (0,0,0,0);
- // Point p2 (10,0,0,1);
- // Point p3 (0,10,0,2);
- // Point p4 (10,10,10,3);
- // Point p5 (5,5,10,4);
- //
- // std::vector<Point> points = {p1,p2,p3,p4,p5};
- //
- // std::vector<Triangle> faces;
- // GiftWrapping(points, faces);
- Start();
- return 0;
- }
- // std::sort(points.begin(), points.end(), [](const Point& p1, const Point& p2){ return p1.number <= p2.number ; });
- // auto last = std::unique(points.begin(), points.end());
- // points.erase(last, points.end());
- //
- // for (auto point : points) {
- // point.Print();
- // }
- //
- // std::cout<<'\n';
- //
- // Edge edge(p1,p3,p5);
- // Triangle triangle(edge, p5);
- // std::vector<Point> point_tr = GetPointsOfTriangle(triangle);
- // for (auto point : point_tr) {
- // point.Print();
- // }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement