Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define all(x) (x).begin(),(x).end()
- using namespace std;
- using ll = long long;
- struct pt {
- int x, y, ind;
- pt(int cx = 0, int cy = 0, int cind = 0) {
- x = cx;
- y = cy;
- ind = cind;
- }
- bool operator < (const pt& o) {
- return x < o.x || (x == o.x && y < o.y);
- }
- pt operator - (const pt& o) const {
- return pt(x - o.x, y - o.y);
- }
- ll norm() {
- return 1ll * x * x + 1ll * y * y;
- }
- };
- // abc
- ll cw(pt a, pt b, pt c) {
- pt v1 = a - b;
- pt v2 = c - b;
- return 1ll * v1.x * v2.y - 1ll * v1.y * v2.x;
- }
- vector<pt> ConvexHull(vector<pt> arr) {
- sort(all(arr));
- sort(arr.begin() + 1, arr.end(), [&] (const pt& a, const pt& b) {
- ll cw_val = cw(a, arr[0], b);
- return cw_val < 0 || (cw_val == 0 && (a - arr[0]).norm() < (b - arr[0]).norm());
- });
- vector<pt> ans = {arr[0]};
- for (int i = 1; i < (int)arr.size(); i++) {
- pt& cur = arr[i];
- while (ans.size() > 1) {
- auto v = ans.back();
- auto u = ans[(int)ans.size() - 2];
- if (cw(u, v, cur) <= 0) {
- ans.pop_back();
- } else {
- break;
- }
- }
- ans.push_back(cur);
- }
- pt& cur = arr[0];
- while (ans.size() > 1) {
- auto v = ans.back();
- auto u = ans[(int)ans.size() - 2];
- if (cw(u, v, cur) <= 0) {
- ans.pop_back();
- } else {
- break;
- }
- }
- return ans;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n;
- cin >> n;
- vector<pt> arr(n);
- for (int i = 0; i < n; i++) {
- cin >> arr[i].x >> arr[i].y;
- arr[i].ind = i;
- }
- vector<pt> result = ConvexHull(arr);
- int mx = 0;
- for (auto [x, y, ind] : result) mx = max(ind, mx);
- bool good = false;
- n = result.size();
- for (int i = 0; i < (int) result.size(); i++) {
- if (result[i].ind == mx) {
- if (result[(i + 1) % n].ind > result[(i + n - 1) % n].ind) {
- good = false;
- } else {
- good = true;
- }
- }
- }
- cout << (good ? "cw" : "ccw") << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement