Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2020
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.10 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define double long double
  3. #define int long long
  4. using namespace std;
  5.  
  6. const double EPS = 1e-8;
  7.  
  8. template<typename T> struct Vector {
  9.     T x, y;
  10.     Vector(T x = 0, T y = 0): x(x), y(y) {};
  11.  
  12.     Vector operator+ (const Vector &other) {
  13.         return Vector(x + other.x, y + other.y);
  14.     }
  15.     Vector operator- (const Vector &other) {
  16.         return Vector(x - other.x, y - other.y);
  17.     }
  18.     T operator* (const Vector &other) {
  19.         return x * other.x + y * other.y;
  20.     }
  21.     Vector operator* (const double &other) {
  22.         return Vector(x * other, y * other);
  23.     }
  24.     T operator% (const Vector &other) {
  25.         return x * other.y - y * other.x;
  26.     }
  27.     double abs() {
  28.         return sqrt(x * x + y * y);
  29.     }
  30.     istream & operator>> (istream & in) {
  31.         T x_, y_;
  32.         in >> x_ >> y_;
  33.         x = x_, y = y_;
  34.         return in;
  35.     }
  36. };
  37.  
  38. template<typename T> struct Point {
  39.     T x, y;
  40.     Point(T x = 0, T y = 0): x(x), y(y) {};
  41.  
  42.     Point operator+ (const Vector<T> &other) {
  43.         return Point(x + other.x, y + other.y);
  44.     }
  45.     Vector<T> operator- (const Point &B) {
  46.         return Vector<T>(x - B.x, y - B.y);
  47.     }
  48.     bool operator< (const Point &B) {
  49.         return (B.x == x ? y < B.y : x < B.x);
  50.     }
  51. };
  52.  
  53. template<typename T> bool cw(Vector<T> A, Vector<T> B) {
  54.     return (A % B < -EPS);
  55. }
  56.  
  57. template<typename T> bool ccw(Vector<T> A, Vector<T> B) {
  58.     return (A % B > EPS);
  59. }
  60.  
  61. template<typename T> double dist(Point<T> A, Point<T> Q, Point<T> P) {
  62.     if ((A - Q) * (P - Q) < 0) return min((A - P).abs(), (A - Q).abs());
  63.     return abs((A - P) % (Q - P)) / (Q - P).abs();
  64. }
  65.  
  66. template<typename T> istream & operator>> (istream & in, Point<T> &a) {
  67.     T x_, y_;
  68.     in >> x_ >> y_;
  69.     a.x = x_, a.y = y_;
  70.     return in;
  71. }
  72.  
  73. signed main() {
  74.     ios::sync_with_stdio(0);
  75.     cin.tie(0);
  76.     freopen("hull.in", "r", stdin);
  77.     freopen("hull.out", "w", stdout);
  78.     vector<Point<int>> lower, upper, all_points;
  79.     int n;
  80.     cin >> n;
  81.     all_points.resize(n);
  82.     for (int i = 0; i < n; i++) cin >> all_points[i];
  83.     sort(all_points.begin(), all_points.end());
  84.     Vector<int> pivot = all_points.back() - all_points.front();
  85.     for (int i = 0; i < n; i++) {
  86.         if (i == 0 || i == n - 1) upper.push_back(all_points[i]), lower.push_back(all_points[i]);
  87.         else if (cw(all_points[i] - all_points.front(), pivot)) upper.push_back(all_points[i]);
  88.         else lower.push_back(all_points[i]);
  89.     }
  90.     vector<Point<int>> uh, lh;
  91.     for (int i = 0; i < upper.size(); i++) {
  92.         while(uh.size() > 1 && !cw(uh.back() - uh[uh.size() - 2], upper[i] - uh.back())) uh.pop_back();
  93.         uh.push_back(upper[i]);
  94.     }
  95.     for (int i = 0; i < lower.size(); i++) {
  96.         while(lh.size() > 1 && !ccw(lh.back() - lh[lh.size() - 2], lower[i] - lh.back())) lh.pop_back();
  97.         lh.push_back(lower[i]);
  98.     }
  99.     cout << lh.size() + uh.size() - 2 << "\n";
  100.     for (auto i : lh) cout << i.x << " " << i.y << "\n";
  101.     for (int i = uh.size() - 2; i >= 1; i--) cout << uh[i].x << " " << uh[i].y << "\n";
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement