QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253431#800. TrianglesCamillus#0 0ms0kbC++202.2kb2023-11-16 23:54:142024-07-04 02:51:36

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 02:51:36]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-11-16 23:54:14]
  • 提交

answer

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

#ifdef LOCAL
int get_n();
bool is_clockwise(int a, int b, int c);
void give_answer(int s);
#else
#   include "trilib.h"
#endif

using namespace std;

random_device rd;
mt19937_64 rnd(rd());

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;
            }
        }
    }

    vector<int> D = A;

    B.erase(B.begin());
    B.pop_back();

    D.insert(D.end(), B.begin(), B.end());

    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++;
        }
    }

    give_answer(cnt - m);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

3
-843737031 -842526876
951189384 673353567
-450418999 301219510

output:

Unauthorized output

result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Runtime Error

Test #97:

score: 0
Runtime Error

input:

3
498999289 500164826
0 0
-501000711 1000000000

output:

Unauthorized output

result:


Subtask #5:

score: 0
Skipped

Dependency #1:

0%