Advertisement
Dimaush

Untitled

Dec 26th, 2022
860
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.93 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5.  
  6. class TPoint {
  7. private:
  8.     int X, Y;
  9.  
  10.     friend class TSetOfPoints;
  11.     friend bool operator==(const TPoint&, const TPoint&);
  12.     friend int CrossProduct(const TPoint&, const TPoint&);
  13.  
  14. public:
  15.     TPoint(int x = 0, int y = 0) : X(x), Y(y) {}
  16.  
  17.     int Length() const {
  18.         return X * X + Y * Y;
  19.     }
  20.  
  21.     const TPoint operator-() const {
  22.         return TPoint(-X, -Y);
  23.     }
  24.  
  25.     const TPoint& operator+=(TPoint p) {
  26.         X += p.X;
  27.         Y += p.Y;
  28.         return *this;
  29.     }
  30.  
  31.     const TPoint& operator-=(TPoint p) {
  32.         *this += -p;
  33.         return *this;
  34.     }
  35.  
  36.     void Print(std::ostream& stream) {
  37.         stream << X << " " << Y << "\n";
  38.     }
  39. };
  40.  
  41. const TPoint operator-(const TPoint& p1, const TPoint& p2) {
  42.     TPoint p = p1;
  43.     p -= p2;
  44.     return p;
  45. }
  46.  
  47. bool operator==(const TPoint& p1, const TPoint& p2) {
  48.     return p1.X == p2.X && p1.Y == p2.Y;
  49. }
  50.  
  51. int CrossProduct(const TPoint& p1, const TPoint& p2) {
  52.     return p1.X * p2.Y - p1.Y * p2.X;
  53. }
  54.  
  55. bool operator<(TPoint p1, TPoint p2) {
  56.     return CrossProduct(p1, p2) > 0 || (CrossProduct(p1, p2) == 0 && p1.Length() < p2.Length());
  57. }
  58.  
  59. class TSetOfPoints {
  60. private:
  61.     unsigned Amount;
  62.     std::vector<TPoint> Set;
  63.  
  64. public:
  65.     TSetOfPoints(unsigned a) : Amount(a), Set(Amount) {}
  66.  
  67.     void ReadFromStream(std::istream& stream) {
  68.         for (auto iter = Set.begin(); iter != Set.end(); ++iter) {
  69.             stream >> iter->X >> iter->Y;
  70.         }
  71.     }
  72.  
  73.     unsigned GetSize() const {
  74.         return Amount;
  75.     }
  76.  
  77.     std::vector<TPoint> ConvexHull() const {
  78.         std::vector<TPoint> points = Set;
  79.  
  80.         TPoint z = points[0];
  81.         for (TPoint p : points) {
  82.             TPoint t = z - p;
  83.             if (t.Y > 0 || (t.Y == 0 && t.X > 0)) {
  84.                 z = p;
  85.             }
  86.         }
  87.  
  88.         for (TPoint &p : points) {
  89.             p -= z;
  90.         }
  91.         std::sort(points.begin(), points.end());
  92.         auto last = std::unique(points.begin(), points.end());
  93.         points.erase(last, points.end());
  94.  
  95.         std::vector<TPoint> hull;
  96.         for (TPoint p : points) {
  97.             while (hull.size() >= 2 && CrossProduct(hull[hull.size() - 2] - hull.back(), p - hull.back()) >= 0) {
  98.                  hull.pop_back();
  99.             }
  100.             hull.push_back(p);
  101.         }
  102.         for (TPoint &p : hull) {
  103.             p += z;
  104.         }
  105.         return hull;
  106.     }
  107. };
  108.  
  109. TSetOfPoints Create(std::istream& stream) {
  110.     unsigned n;
  111.     std::cin >> n;
  112.     TSetOfPoints t(n);
  113.     t.ReadFromStream(stream);
  114.     return t;
  115. }
  116.  
  117. int main() {
  118.     TSetOfPoints s = Create(std::cin);
  119.     std::vector<TPoint> h = s.ConvexHull();
  120.     std::cout << h.size() << std::endl;
  121.     if (s.GetSize() & 1) {
  122.         std::reverse(h.begin(), h.end());
  123.     }
  124.     for (TPoint p : h) {
  125.         p.Print(std::cout);
  126.     }
  127.     return 0;
  128. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement