QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253447#800. TrianglesCamillus#0 13ms5052kbC++204.0kb2023-11-17 00:30:282024-07-04 02:51:46

Judging History

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

  • [2024-07-04 02:51:46]
  • 评测
  • 测评结果:0
  • 用时:13ms
  • 内存:5052kb
  • [2023-11-17 00:30:28]
  • 提交

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 (!Q.contains(l) && is_clockwise(D[l], D[r], D[pr(l)])) {
            Q.insert(l);
            l = pr(l);
        } else if (!Q.contains(r) && 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
Wrong Answer

Test #1:

score: 15
Accepted
time: 0ms
memory: 4108kb

input:

3
-843737031 -842526876
951189384 673353567
-450418999 301219510

output:

3

result:

ok single line: '3'

Test #2:

score: -15
Wrong Answer
time: 0ms
memory: 3828kb

input:

50
4 -2
1 -1
7 49
11 121
9 81
144 -12
-121 11
-25 5
15 225
-49 7
-4 -16
196 -14
-144 12
225 -15
16 256
-13 -169
-14 -196
-8 -64
16 -4
-1 -1
81 -9
1 1
14 196
-196 14
169 -13
8 64
2 4
-15 -225
-225 15
12 144
49 -7
5 25
-64 8
-2 -4
-9 -81
13 169
121 -11
25 -5
-5 -25
-16 4
-12 -144
64 -8
-81 9
-169 13
-...

output:

10

result:

wrong answer 1st lines differ - expected: '4', found: '10'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #97:

score: 20
Accepted
time: 0ms
memory: 4108kb

input:

3
498999289 500164826
0 0
-501000711 1000000000

output:

3

result:

ok single line: '3'

Test #98:

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

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: 0ms
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: 3948kb

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: 4148kb

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: 4080kb

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: 10ms
memory: 4568kb

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: 3816kb

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: 3968kb

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: 3816kb

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: 4112kb

input:

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

output:

5

result:

ok single line: '5'

Test #109:

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

input:

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

output:

5

result:

ok single line: '5'

Test #110:

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

input:

6
-249429260 499878130
-500618712 1000000000
-750169917 667985057
0 0
-1000000000 333791081
-423987992 441135671

output:

5

result:

ok single line: '5'

Test #111:

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

input:

6
-332582928 500725139
166933730 1000000000
667417072 665597070
0 0
273901801 374457591
333874158 331964553

output:

5

result:

ok single line: '5'

Test #112:

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

input:

6
749513925 750358345
0 0
733397885 734233471
249966058 250696070
499439211 500652752
1000000000 1000000000

output:

5

result:

ok single line: '5'

Test #113:

score: 0
Accepted
time: 13ms
memory: 4788kb

input:

39928
-476522026 551730387
224891540 171577343
-113877659 929569975
-203353341 150152890
198921935 147744261
308438536 742910689
-53655745 31604487
158140984 112034902
201777750 846235753
-193199635 141108786
-334309834 727379072
-430696847 394152056
124242704 912018484
257601588 794029365
-19506951...

output:

39928

result:

ok single line: '39928'

Test #114:

score: 0
Accepted
time: 13ms
memory: 4872kb

input:

39941
240554968 185062872
447645732 417276294
-491125898 517132655
368128061 682261344
473988500 545175998
-122366979 82607281
481654798 467242405
81278725 949027035
147955699 896869442
-285790435 770058648
-430695864 394168061
126271619 914556205
41396791 23515280
-228685763 825407987
49571329 9712...

output:

39940

result:

ok single line: '39940'

Test #115:

score: 0
Accepted
time: 13ms
memory: 4668kb

input:

39926
-142378555 98621088
-325394629 735660926
327699106 275018065
-489696976 528039827
481194989 470881153
24931815 13296058
473246909 543185134
488791191 518478648
94595699 61053528
483527197 527202941
469748725 548407248
70518821 952546153
-500692532 500047646
157977796 884285698
-343722772 29115...

output:

39926

result:

ok single line: '39926'

Test #116:

score: 0
Accepted
time: 12ms
memory: 4808kb

input:

39955
261822639 204158512
-475550649 460358621
-335602958 715847304
266887451 790691711
-63556883 38627155
403937398 358055405
432204044 393564249
398775140 351802869
78622062 951499945
16332118 992224256
205017926 848703710
493950199 516752397
456420322 426063705
-92587743 59701729
347057311 292241...

output:

39954

result:

ok single line: '39954'

Test #117:

score: 0
Accepted
time: 9ms
memory: 4836kb

input:

39948
462511423 433979231
-473759331 453767275
-90598582 57900980
-320836324 265121526
423067024 608652338
488614734 473989701
-235144749 179576796
30889537 16474888
-469825001 447865050
423913411 607558876
-135921489 92959954
162433501 880044726
-481886992 535515410
219280475 163092447
185556733 13...

output:

39948

result:

ok single line: '39948'

Test #118:

score: 0
Accepted
time: 13ms
memory: 4968kb

input:

39983
-297064710 750481437
-472950080 536181826
-444511696 411997270
234261119 178799352
371473860 686934082
-328163255 272851468
29611810 989922085
-138402537 896981374
348436732 712949934
-412186078 619857557
-234639058 178835702
355330018 705278839
-223873725 822231072
470199227 448163968
-132808...

output:

39982

result:

ok single line: '39982'

Test #119:

score: 0
Accepted
time: 13ms
memory: 4716kb

input:

39999
75496842 47039832
268243441 790263429
30326832 984735456
-209669325 842079603
468860646 450257755
-474556765 544678664
155310598 109887433
-73188123 45051470
-315251144 259448235
-25109934 985436228
465071348 444590709
-227486014 825757660
425276434 615632566
-75408940 951773738
-316891291 261...

output:

39999

result:

ok single line: '39999'

Test #120:

score: 0
Accepted
time: 13ms
memory: 4784kb

input:

39966
-163562797 887570254
-105289983 69753861
316787630 736177558
-424002630 619416642
278293061 775555590
-335677512 722718140
-410851185 371250307
335110822 281461499
397700443 645367200
23746931 984704027
-368688286 686029690
291511428 235468877
-264416222 209605430
191576248 140448137
220059596...

output:

39965

result:

ok single line: '39965'

Test #121:

score: 0
Accepted
time: 13ms
memory: 4936kb

input:

40000
164228817 114985033
470748168 442975934
-336897893 283090565
501649401 495570574
-76907883 952105469
285554518 769815118
-245981358 808246389
-421168036 381951796
-157346877 110863194
408576437 360647764
-421337820 382168352
438723154 593256356
-165288741 117570705
104381865 931130775
-4345879...

output:

40000

result:

ok single line: '40000'

Test #122:

score: 0
Accepted
time: 13ms
memory: 4964kb

input:

39990
155519328 475998776
-58248659 958804308
-411516034 369786577
115278403 76353352
-331286101 276719047
-427341681 597918147
477136725 550499188
477733800 549595294
385624593 670236436
282451482 224954270
-300906959 744481559
485206154 467723441
-64431703 39006106
-493711877 497579395
-470151737 ...

output:

39989

result:

ok single line: '39989'

Test #123:

score: 0
Accepted
time: 13ms
memory: 4616kb

input:

39997
226617428 173560892
-320556655 264836397
471111895 454190254
264188489 790822331
45661284 974137511
-150280752 895727317
289885314 235510068
74138909 954414758
-466803809 442826425
-415780873 374304072
-333695708 722693864
270657108 216100042
316145407 262922546
-260622808 204042831
-449636278...

output:

39997

result:

ok single line: '39997'

Test #124:

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

input:

3
501045942 499523716
-498954058 1000000000
0 0

output:

3

result:

ok single line: '3'

Test #125:

score: 0
Accepted
time: 8ms
memory: 4600kb

input:

39980
-39942614 980609689
470007724 449308195
239446951 183644802
305522947 745838282
139201766 95340251
-27238919 14761249
-36598780 982703796
136595125 902516229
367476169 317270113
78504625 947555550
437202182 403037894
366540041 679148063
-60418084 967131140
-41339481 979724095
-292345754 236815...

output:

39979

result:

ok single line: '39979'

Test #126:

score: 0
Accepted
time: 13ms
memory: 4868kb

input:

39997
-16309717 986093591
-83329153 940687543
-367918842 317509199
-171512782 122626967
-62288761 955915408
-297295153 240893874
337200697 726317718
130392034 89057956
500079898 512522189
96155602 945192821
-38393064 21657089
71456613 44093433
-382261600 658588025
133324946 91430850
-198617954 14634...

output:

39997

result:

ok single line: '39997'

Test #127:

score: 0
Accepted
time: 13ms
memory: 4812kb

input:

39991
-431941480 599692834
354931089 703773824
432774548 397117393
-61963457 959355841
60641466 36499250
40875374 979973653
-72174850 44622201
236544140 824002659
-385696623 340908027
-363348582 314671479
-126827889 910637042
-23976613 984354508
-63253242 38327227
446825562 415846224
347954504 29562...

output:

39990

result:

ok single line: '39990'

Test #128:

score: 0
Accepted
time: 13ms
memory: 4820kb

input:

39994
-486084514 473101573
-316048747 260656229
-154021934 894671567
213378080 158873752
-359958997 308486699
-184370095 868666035
-357804880 306068798
114519846 920868235
-500243129 499283923
-39886773 22643981
-490055656 520686617
45516494 971120918
248159525 803970138
108653093 71167746
278330877...

output:

39994

result:

ok single line: '39994'

Test #129:

score: 0
Accepted
time: 13ms
memory: 4800kb

input:

39996
-1945954 994620804
308293896 251856285
-328026775 716637702
-444234988 413893740
-266536769 780750206
238364407 182775808
-71240600 949821952
169430016 120909913
-466503468 445687869
-283882022 227214054
-361461824 679259713
-115845374 915911464
473993040 451831499
-206426457 153117554
1454637...

output:

39995

result:

ok single line: '39995'

Test #130:

score: 0
Accepted
time: 13ms
memory: 4740kb

input:

39996
-482076936 539453255
474276406 461607331
-230992264 825780972
-344104046 294564779
-356993066 698533502
-209025590 845769259
-350582684 705596098
486168124 532274692
-136203335 907726958
495782286 497997205
-12666546 6255940
352475851 703638720
435883070 604282001
-497884599 501682365
-3849412...

output:

39996

result:

ok single line: '39996'

Test #131:

score: 0
Accepted
time: 13ms
memory: 4688kb

input:

39997
-240259695 185725748
178277378 869705176
-477010805 461001091
-113079502 927795361
76361402 47584549
179403937 129593876
188255222 137357251
-320901293 267034601
252456811 802119721
-443462250 412910579
381475460 666042195
-361945186 312302574
402916134 360553156
348168698 703796147
-410220724...

output:

39996

result:

ok single line: '39996'

Test #132:

score: 0
Accepted
time: 13ms
memory: 4968kb

input:

39999
-75428217 46872579
-452904755 583998410
175132576 128711150
313705679 264574184
166156016 884490313
-208335849 156077079
-124837074 915489894
271490156 220200923
-77111814 48091872
-34805875 979493589
-7815198 3530007
-329194121 729064565
-375638531 678500567
67589149 41979837
-147460247 89750...

output:

39999

result:

ok single line: '39999'

Test #133:

score: 0
Accepted
time: 13ms
memory: 4928kb

input:

39999
-263411287 207360111
462924986 438209614
113453111 932691882
-424620876 602316018
297646595 241622949
-368587575 670256971
-460699210 436758163
325952198 739173257
-43454630 967667050
-332325383 278582770
-333298178 709782026
394643855 661435840
247690882 191997675
428574217 619301747
36515089...

output:

39998

result:

ok single line: '39998'

Test #134:

score: 0
Accepted
time: 8ms
memory: 5052kb

input:

40000
-258676586 791774157
121835745 919842433
-158649637 111156577
473825412 448310193
-39113338 22026446
-88629000 56128787
441244190 589303068
-349980366 295132795
438550608 399425784
-138553652 900769354
169639420 880111697
349079785 292638440
296499815 237223526
-224881858 169223198
429813489 3...

output:

40000

result:

ok single line: '40000'

Test #135:

score: 0
Accepted
time: 13ms
memory: 4744kb

input:

40000
130927778 370193535
-291520891 770455734
280001175 222189113
396636955 643261964
186643405 135173087
-138743386 910099794
339994428 284544948
-396554476 353908114
350490620 296095592
381967466 331999783
467362647 549878001
-448475692 587690552
425172181 384919733
-19379792 10138824
-149177660 ...

output:

39999

result:

ok single line: '39999'

Test #136:

score: 0
Accepted
time: 4ms
memory: 4788kb

input:

40000
0 -1000000000
1 -999999999
2 -999999996
3 -999999991
4 -999999984
5 -999999975
6 -999999964
7 -999999951
8 -999999936
9 -999999919
10 -999999900
11 -999999879
12 -999999856
13 -999999831
14 -999999804
15 -999999775
16 -999999744
17 -999999711
18 -999999676
19 -999999639
20 -999999600
21 -99999...

output:

40000

result:

ok single line: '40000'

Test #137:

score: -20
Wrong Answer
time: 11ms
memory: 4652kb

input:

40000
39999 599920001
39998 599840004
39997 599760009
39996 599680016
39995 599600025
39994 599520036
39993 599440049
39992 599360064
39991 599280081
39990 599200100
39989 599120121
39988 599040144
39987 598960169
39986 598880196
39985 598800225
39984 598720256
39983 598640289
39982 598560324
39981 ...

output:

Too many queries!!!!@QingyuSecretT0ken123456J0fdj1n2410Bfnf
40000

result:

wrong answer 1st lines differ - expected: '40000', found: 'Too many queries!!!!@QingyuSecretT0ken123456J0fdj1n2410Bfnf'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%