QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253445#800. TrianglesCamillus#0 7ms4764kbC++203.9kb2023-11-17 00:26:312024-07-04 02:51:46

Judging History

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

  • [2024-07-04 02:51:46]
  • 评测
  • 测评结果:0
  • 用时:7ms
  • 内存:4764kb
  • [2023-11-17 00:26:31]
  • 提交

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(6);

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();
    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

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: 20
Accepted
time: 1ms
memory: 3780kb

input:

3
498999289 500164826
0 0
-501000711 1000000000

output:

3

result:

ok single line: '3'

Test #98:

score: 0
Accepted
time: 1ms
memory: 3836kb

input:

122
-135326308 856066522
-88326696 904066294
-353311117 441507355
-176561051 159964959
-88434983 79851007
397766606 578255587
-103992077 888097153
194293623 185454709
195268652 797975052
299007352 286809990
-229443984 759548192
-263934443 240109169
-404993259 370300463
490741999 475479289
-123667348...

output:

121

result:

ok single line: '121'

Test #99:

score: 0
Accepted
time: 1ms
memory: 3836kb

input:

178
-10518957 10030339
-396577929 397502614
-354781959 632233830
-281457444 696316408
344017930 735726622
220693114 856918991
-241311839 239328630
-95047326 92798774
282407306 796482891
74131237 83289310
470219345 541757867
452805360 627255661
31909720 35677649
-37709503 906709611
346219561 39591212...

output:

178

result:

ok single line: '178'

Test #100:

score: 0
Accepted
time: 1ms
memory: 3980kb

input:

1724
435674967 569734141
-344223292 664794715
-371182565 636678076
-59380815 947913711
265677747 744373156
-431055657 573450807
64708196 57849142
-140934693 869383073
488788510 511916672
418946398 587517529
16220609 14001831
432304161 573332280
165312888 152492955
426760030 579230072
-115003278 8945...

output:

1724

result:

ok single line: '1724'

Test #101:

score: 0
Accepted
time: 1ms
memory: 3816kb

input:

1100
172141224 162926453
-129742135 903504912
-138847862 894710752
434251089 427318806
385178810 376249510
-32778561 28627008
-352618914 682197217
-124303061 908741673
-396971795 374472836
-392911675 640833898
304243004 663526969
438289585 517977228
192808494 183114268
-1050787 975564667
-442530480 ...

output:

1100

result:

ok single line: '1100'

Test #102:

score: 0
Accepted
time: 3ms
memory: 4084kb

input:

7604
344487273 646600702
-518930288 500151075
52125135 940464104
-5588256 3892993
-169734063 871183114
178214687 820412440
132590346 865042064
238696099 759232524
-481597137 552776352
-1076022 986810978
120775550 876391248
26381090 963422465
380843851 605960794
248726367 748872324
-287065564 7592190...

output:

7604

result:

ok single line: '7604'

Test #103:

score: 0
Accepted
time: 2ms
memory: 4028kb

input:

5273
-294028765 709996963
-205420737 799978394
456624977 584338139
463857567 576489643
-313748261 689407920
-395562316 601477782
128923185 903092890
-277370073 727243217
-337040355 664788200
-292898864 711171615
428883164 614006198
194199760 844071801
23353499 18625022
-258215740 746868884
180108932...

output:

5272

result:

ok single line: '5272'

Test #104:

score: 0
Accepted
time: 7ms
memory: 4764kb

input:

32317
-237187362 483833038
-201759621 848171215
300520727 250775195
30061742 981065412
410166728 625028467
48768023 968366905
10221009 5287286
-361078045 316666973
332612689 284893749
-222568096 174558210
447312093 421837582
-415262375 380421739
302943829 745169983
61437871 959313553
-43871384 97517...

output:

32316

result:

ok single line: '32316'

Test #105:

score: 0
Accepted
time: 0ms
memory: 4092kb

input:

6
666756564 668566198
0 0
-333243436 499213296
166714395 1000000000
333096851 333498115
220870883 353572786

output:

5

result:

ok single line: '5'

Test #106:

score: 0
Accepted
time: 0ms
memory: 4128kb

input:

6
516060012 518525684
0 0
500732558 1000000000
750692466 666349426
250641212 500782157
1000000000 332728079

output:

5

result:

ok single line: '5'

Test #107:

score: 0
Accepted
time: 0ms
memory: 4116kb

input:

6
-715666952 442384255
-750449397 666015713
-499403819 1000000000
-249026204 500106636
0 0
-1000000000 332646804

output:

5

result:

ok single line: '5'

Test #108:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

6
154336691 188058821
1000000000 666141970
501648357 332968552
0 0
667499672 1000000000
334145828 500727904

output:

5

result:

ok single line: '5'

Test #109:

score: -20
Runtime Error

input:

6
498734119 1000000000
-251037445 332876405
-501265881 665829221
250154255 500184857
-69341346 663798009
0 0

output:

Unauthorized output

result:


Subtask #5:

score: 0
Skipped

Dependency #1:

0%