QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253436#800. TrianglesCamillus#0 13ms4992kbC++203.0kb2023-11-17 00:06:002024-07-04 02:51:40

Judging History

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

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

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

    give_answer(m - cnt);
    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: 4112kb

input:

3
-843737031 -842526876
951189384 673353567
-450418999 301219510

output:

3

result:

ok single line: '3'

Test #2:

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

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:

11

result:

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

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

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

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

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

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: 2ms
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: 3956kb

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

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

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

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

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

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

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

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: 9ms
memory: 4640kb

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

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

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: 13ms
memory: 4708kb

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: 13ms
memory: 4676kb

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: 12ms
memory: 4736kb

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

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

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

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

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

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

input:

3
501045942 499523716
-498954058 1000000000
0 0

output:

3

result:

ok single line: '3'

Test #125:

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

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: 9ms
memory: 4716kb

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

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: 8ms
memory: 4992kb

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: 12ms
memory: 4700kb

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

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: 12ms
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: 12ms
memory: 4780kb

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

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: 12ms
memory: 4748kb

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

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: -20
Wrong Answer
time: 10ms
memory: 4572kb

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:

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%