QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253453#800. TrianglesCamillus#Compile Error//C++203.9kb2023-11-17 00:32:142024-07-04 02:25:52

Judging History

This is the latest submission verdict.

  • [2024-07-04 02:25:52]
  • Judged
  • [2023-11-17 00:32:14]
  • Submitted

answer

/// @author Camillus <3
#include "bits/stdc++.h"

#ifdef LOCAL

struct Point {
    int x = 0, y = 0;

    Point() = default;
    Point(int x, int y) : x(x), y(y) {}
    Point(const Point &A, const Point &B) {
        x = B.x - A.x;
        y = B.y - A.y;
    }

    Point operator+(const Point &other) const {
        return {x + other.x, y + other.y};
    }

    Point operator-(const Point &other) const {
        return {x - other.x, y - other.y};
    }

    int64_t operator%(const Point &other) const {
        return 1ll * x * other.y - 1ll * y * other.x;
    }
};

std::vector<Point> P;

int get_n() {
    int n;
    std::cin >> n;

    P.resize(n + 1);

    for (int i = 1; i <= n; i++) {
        std::cin >> P[i].x >> P[i].y;
    }

    return n;
}

bool is_clockwise(int a, int b, int c) {
    Point A = P[a];
    Point B = P[b];
    Point C = P[c];

    return Point(A, B) % Point(A, C) < 0;
}

void give_answer(int s) {
    std::cout << s << '\n';
    exit(0);
}

#else
#   include "trilib.h"
#endif

using namespace std;

random_device rd;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int n) {
    return rnd() % n;
}

int rand(int l, int r) {
    return l + rand(r - l + 1);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = get_n();

    int u = rand(1, n);
    int v = rand(1, n - 1);

    if (v >= u) {
        v++;
    }

    vector<int> A, B;

    for (int x = 1; x <= n; x++) {
        if (x != u && x != v) {
            if (is_clockwise(u, v, x)) {
                A.push_back(x);
            } else {
                B.push_back(x);
            }
        }
    }

    sort(A.begin(), A.end(), [&u](int x, int y) {
        return is_clockwise(u, y, x);
    });

    sort(B.begin(), B.end(), [&v](int x, int y) {
        return is_clockwise(v, y, x);
    });

    vector<int> hullA = {u};
    A.push_back(v);

    for (int c : A) {
        while (hullA.size() >= 2) {
            int b = hullA[hullA.size() - 1];
            int a = hullA[hullA.size() - 2];

            if (is_clockwise(a, b, c)) {
                hullA.pop_back();
            } else {
                break;
            }
        }
        hullA.push_back(c);
    }

    vector<int> hullB = {v};
    B.push_back(u);

    for (int c : B) {
        while (hullB.size() >= 2) {
            int b = hullB[hullB.size() - 1];
            int a = hullB[hullB.size() - 2];

            if (is_clockwise(a, b, c)) {
                hullB.pop_back();
            } else {
                break;
            }
        }
        hullB.push_back(c);
    }

    vector<int> D = hullA;
    D.insert(D.end(), hullB.begin() + 1, hullB.end() - 1);

    int cnt = 0;

    int m = D.size();

    for (int i = 0; i < (int)D.size(); i++) {
        int a = D[(i + m - 1) % m];
        int b = D[i];
        int c = D[(i + 1) % m];

        if (is_clockwise(a, b, c)) {
            cnt++;
        }
    }

    auto pr = [&](int i) -> int {
        return (i + m - 1) % m;
    };

    auto nx = [&](int i) -> int {
        return (i + 1) % m;
    };

    int l = 0, r = 1;

    set<int> Q;

    while (true) {
        if (is_clockwise(D[l], D[r], D[pr(l)])) {
            Q.insert(l);
            l = pr(l);
        } else if (is_clockwise(D[l], D[r], D[nx(r)])) {
            cnt++;
            r = nx(r);
            Q.insert(r);
        } else {
            break;
        }
    }

    r = hullA.size() % m;
    l = pr(r);

    while (true) {
        if (is_clockwise(D[l], D[r], D[pr(l)])) {
            Q.insert(l);
            l = pr(l);
        } else if (is_clockwise(D[l], D[r], D[nx(r)])) {
            cnt++;
            r = nx(r);
            Q.insert(r);
        } else {
            break;
        }
    }

    give_answer(m - Q.size());
    return 0;
}

Details