Advertisement
Guest User

фыв

a guest
Nov 20th, 2017
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.12 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define all(x) x.begin(), x.end()
  6. #define endl '\n'
  7. #define sz(x) (int)(x).size()
  8. #define mp(x, y) make_pair(x, y)
  9. #define pb push_back
  10. #define pii pair<int, int>
  11. #define rep(i, f, t) for (auto i = (f); i < (t); ++i)
  12. #define ui unsigned int
  13. #define ll long long
  14. #define double long double
  15. #define ull unsigned long long
  16.  
  17. const int inf = (int)(2e9);
  18. const ll INF = (ll)(1e18);
  19. const int MOD = (int)(1e9 + 7);
  20. const double eps = (double)(1e-9);
  21. const double pi = acos(-1);
  22.  
  23. const int maxn = (int)(1e5 + 10);
  24. const int maxm = (int)(2e5 + 10);
  25.  
  26. void solve();
  27.  
  28. template <typename A> inline void print(A x) { cout << x << endl; }
  29. template <typename A, typename B> inline void print(A x, B y) { cout << x << ' ' << y << endl; }
  30. template <typename A, typename B, typename C> inline void print(A x, B y, C z) { cout << x << ' ' << y << ' ' << z << endl; }
  31. template <typename A> inline void in(A &x) { cin >> x; }
  32. template <typename A, typename B> inline void in(A &x, B &y) { cin >> x >> y; }
  33. template <typename A, typename B, typename C> inline void in(A &x, B &y, C &z) { cin >> x >> y >> z; }
  34. template <typename A, typename B, typename C, typename D> inline void in(A &x, B &y, C &z, D &p) { cin >> x >> y >> z >> p; }
  35. template <typename A> inline void read(A begin, A end) { while (begin != end) cin >> *(begin++); }
  36. template <typename A> inline void write(A begin, A end) { while (begin != end) { cout << *(begin++) << ' '; } cout << endl; }
  37.  
  38. ll power(ll a, ll b)
  39. {
  40.     if (b == 0) return 1;
  41.     if (b & 1) return power(a, b - 1) * a;
  42.     ll tmp = power(a, b / 2);
  43.     return tmp * tmp;
  44. }
  45.  
  46. void use_files(string s) {
  47.     freopen(string(s + ".in").c_str(), "r", stdin);
  48.     freopen(string(s + ".out").c_str(), "w", stdout);
  49. }
  50.  
  51. signed main()
  52. {
  53.     std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  54.     srand((ui)(time(0)));
  55.     cout << fixed << setprecision(20);
  56.     solve();
  57.     return 0;
  58. }
  59.  
  60. struct point {
  61.     int x;
  62.     int y;
  63. };
  64.  
  65.  
  66. vector<point> arr;
  67.  
  68. bool comp(point& a, point& b)
  69. {
  70.     return atan2(a.y - arr[0].y, a.x - arr[0].x) < atan2(b.y - arr[0].y, b.x - arr[0].x);
  71. }
  72.  
  73.  
  74. inline double len(point& a, point& b)
  75. {
  76.     return sqrt((double)(b.x - a.x) * (double)(b.x - a.x) + (double)(b.y - a.y) * (double)(b.y - a.y));
  77. }
  78.  
  79. int cross_product(point& a, point& b, point& c, point& d)
  80. {
  81.     point x, y;
  82.     x.x = b.x - a.x, x.y = b.y - a.y;
  83.     y.x = d.x - c.x, y.y = d.y - c.y;
  84.     return x.x * y.y - y.x * x.y;
  85. }
  86.  
  87. void solve()
  88. {
  89.     int n;
  90.     cin >> n;
  91.     arr.resize(n);
  92.     rep(i, 0, n) {
  93.         cin >> arr[i].x >> arr[i].y;
  94.     }
  95.     if (n == 1) {
  96.         print(1);
  97.         print(arr[0].x, arr[0].y);
  98.         return;
  99.     }
  100.     rep(i, 0, n) {
  101.         if (arr[i].x < arr[0].x && arr[i].y < arr[0].y)
  102.             swap(arr[i], arr[0]);
  103.     }
  104.     sort(arr.begin() + 1, arr.end(), &comp);
  105.     vector<point> ans;
  106.     ans.push_back(arr[0]);
  107.     ans.push_back(arr[1]);
  108.     rep(i, 2, n) {
  109.         while (sz(ans) > 1 && cross_product(ans[sz(ans) - 2], ans[sz(ans) - 1], ans[sz(ans) - 1], arr[i]) > 0)
  110.             ans.pop_back();
  111.         ans.push_back(arr[i]);
  112.     }
  113.     if (n & 1)
  114.         reverse(all(ans));
  115.     print(sz(ans));
  116.     rep(i, 0, sz(ans))
  117.         print(ans[i].x, ans[i].y);
  118. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement