Guest User

100173 A

a guest
Jan 28th, 2021
42
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using Point = pair<int, int>;
  5.  
  6. const int N = 100100;
  7.  
  8. int n;
  9. pair<int, int> a[N];
  10.  
  11. int det(int a, int b, int c, int d) { return a * d - b * c; }
  12.  
  13. int det(const Point &p, const Point &q, const Point &o) {
  14.     return det(p.first - o.first, p.second - o.second, q.first - o.first, q.second - o.second);
  15. }
  16.  
  17. long long dist(const Point &p, const Point &q)
  18. {
  19.     return 1LL * (p.first - q.first) * (p.first - q.first) + 1LL * (p.second - q.second) * (p.second - q.second);
  20. }
  21.  
  22. int convexHull(Point *a, int n) {
  23.     if(n < 3) return n;
  24.     swap(*a, *min_element(a, a + n));
  25.     sort(a + 1, a + n, [a](const Point &p, const Point &q) {
  26.         auto d = det(p, q, a[0]);
  27.         return d < 0 || d == 0 && dist(p, a[0]) < dist(q, a[0]);
  28.     });
  29.     int h = 1;
  30.     for (int i = 2; i < n; ++i) {
  31.         while (h > 0 && det(a[h - 1], a[h], a[i]) >= 0)
  32.             --h;
  33.         swap(a[++h], a[i]);
  34.     }
  35.     return h + 1;
  36. }
  37.  
  38. int main() {
  39.     scanf("%d", &n);
  40.     for (int i = 0; i < n; ++i)
  41.         scanf("%d%d", &a[i].first, &a[i].second);
  42.     n = convexHull(a, n);
  43.     printf("%d\n", n);
  44.     for (int i = 0; i < n; ++i)
  45.         printf("%d %d\n", a[i].first, a[i].second);
  46.     return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment