Advertisement
999ms

Untitled

Jan 31st, 2020
283
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define all(x) (x).begin(),(x).end()
  3.  
  4. using namespace std;
  5. using ll = long long;
  6.  
  7. struct pt {
  8.     int x, y, ind;
  9.     pt(int cx = 0, int cy = 0, int cind = 0) {
  10.         x = cx;
  11.         y = cy;
  12.         ind = cind;
  13.     }
  14.     bool operator < (const pt& o) {
  15.         return x < o.x || (x == o.x && y < o.y);
  16.     }
  17.     pt operator - (const pt& o) const {
  18.         return pt(x - o.x, y - o.y);
  19.     }
  20.     ll norm() {
  21.         return 1ll * x * x + 1ll * y * y;
  22.     }
  23. };
  24.  
  25. // abc
  26. ll cw(pt a, pt b, pt c) {
  27.     pt v1 = a - b;
  28.     pt v2 = c - b;
  29.     return 1ll * v1.x * v2.y - 1ll * v1.y * v2.x;
  30. }
  31.  
  32. vector<pt> ConvexHull(vector<pt> arr) {
  33.     sort(all(arr));
  34.     sort(arr.begin() + 1, arr.end(), [&] (const pt& a, const pt& b) {
  35.         ll cw_val = cw(a, arr[0], b);
  36.         return cw_val < 0 || (cw_val == 0 && (a - arr[0]).norm() < (b - arr[0]).norm());
  37.     });
  38.     vector<pt> ans = {arr[0]};
  39.     for (int i = 1; i < (int)arr.size(); i++) {
  40.         pt& cur = arr[i];
  41.         while (ans.size() > 1) {
  42.             auto v = ans.back();
  43.             auto u = ans[(int)ans.size() - 2];
  44.             if (cw(u, v, cur) <= 0) {
  45.                 ans.pop_back();
  46.             } else {
  47.                 break;
  48.             }
  49.         }  
  50.         ans.push_back(cur);
  51.     }
  52.     pt& cur = arr[0];
  53.     while (ans.size() > 1) {
  54.         auto v = ans.back();
  55.         auto u = ans[(int)ans.size() - 2];
  56.         if (cw(u, v, cur) <= 0) {
  57.             ans.pop_back();
  58.         } else {
  59.             break;
  60.         }
  61.     }
  62.     return ans;
  63. }
  64.  
  65. int main() {
  66.     ios_base::sync_with_stdio(false);
  67.     cin.tie(nullptr);
  68.     cout.tie(nullptr);
  69.     int n;
  70.     cin >> n;
  71.     vector<pt> arr(n);
  72.     for (int i = 0; i < n; i++) {
  73.         cin >> arr[i].x >> arr[i].y;
  74.         arr[i].ind = i;
  75.     }
  76.     vector<pt> result = ConvexHull(arr);
  77.     int mx = 0;
  78.     for (auto [x, y, ind] : result) mx = max(ind, mx);
  79.     bool good = false;
  80.     n = result.size();
  81.     for (int i = 0; i < (int) result.size(); i++) {
  82.         if (result[i].ind == mx) {
  83.             if (result[(i + 1) % n].ind > result[(i + n - 1) % n].ind) {
  84.                 good = false;
  85.             } else {
  86.                 good = true;
  87.             }
  88.         }
  89.     }
  90.     cout << (good ? "cw" : "ccw") << endl;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement