Advertisement
MathQ_

Untitled

Feb 21st, 2021
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.84 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <vector>
  5.  
  6. typedef long long ll;
  7.  
  8. #define all(x) (x).begin(), (x).end()
  9.  
  10. using namespace std;
  11.  
  12. struct pt {
  13.     ll x, y;
  14.     pt() {
  15.         x = 0; y = 0;
  16.     }
  17.     pt(int _x, int _y) {
  18.         x = _x; y = _y;
  19.     }
  20. };
  21.  
  22. struct vec {
  23.     ll x, y;
  24.     vec(pt p1, pt p2) {
  25.         x = p2.x - p1.x;
  26.         y = p2.y - p1.y;
  27.     }
  28. };
  29.  
  30. ll sign(ll c) {
  31.     if (c == 0) {
  32.         return c;
  33.     } else {
  34.         return c / abs(c);
  35.     }
  36. }
  37.  
  38. ostream& operator<<(ostream& out, pt &p) {
  39.     out << p.x << " " << p.y;
  40.     return out;
  41. }
  42.  
  43. bool operator==(pt p1, pt p2) {
  44.     return p1.x == p2.x && p1.y == p2.y;
  45. }
  46.  
  47. int operator%(vec v1, vec v2) {
  48.     return sign(v1.x * v2.y - v1.y * v2.x);
  49. }
  50.  
  51. lb angle(pt p) {
  52.     return atan2(p.y, p.x);
  53. }
  54.  
  55. bool comp(pt p1, pt p2) {
  56.     ll c = vec(p1, pt()) % vec(p2, pt());
  57.     if (c == 0) {
  58.         return p1.x * p1.x + p1.y * p1.y < p2.x * p2.x + p2.y * p2.y;
  59.     } else {
  60.         return c > 0;
  61.     }
  62. }
  63.  
  64. int main() {
  65.     int n;
  66.     cin >> n;
  67.     vector<pt> pts(n);
  68.     pt mini(1e9 + 1, 1e9 + 1);
  69.     for (int i = 0; i < n; ++i) {
  70.         cin >> pts[i].x >> pts[i].y;
  71.         if (pts[i].y < mini.y || (pts[i].y == mini.y && pts[i].x < mini.x)) {
  72.             mini = pts[i];
  73.         }
  74.     }
  75.     sort(all(pts), comp);
  76.  
  77.     vector<pt> ans;
  78.     ans.push_back(mini);
  79.     for (int i = 0; i < n; ++i) {
  80.         if (pts[i] == ans.back() || pts[i] == mini) continue;
  81.         while (ans.size() >= 2 && vec(ans[ans.size() - 1], ans[ans.size() - 2]) % vec(ans[ans.size() - 1], pts[i]) >= 0) {
  82.             ans.pop_back();
  83.         }
  84.         ans.push_back(pts[i]);
  85.     }
  86.     n = ans.size();
  87.     cout << n << '\n';
  88.     for (int i = 0; i < n; ++i) {
  89.         cout << ans[i].x << " " << ans[i].y << '\n';
  90.  
  91.     }
  92.     return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement