QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253442#800. TrianglesCamillus#0 10ms4100kbC++203.7kb2023-11-17 00:15:492024-07-04 02:51:44

Judging History

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

  • [2024-07-04 02:51:44]
  • 评测
  • 测评结果:0
  • 用时:10ms
  • 内存:4100kb
  • [2023-11-17 00:15:49]
  • 提交

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;

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

    auto get = [&]() {
        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++;
            }
        }

        return m - cnt;
    };

    give_answer(min({get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get(), get()}));
    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: 3820kb

input:

3
-843737031 -842526876
951189384 673353567
-450418999 301219510

output:

3

result:

ok single line: '3'

Test #2:

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

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:

4

result:

ok single line: '4'

Test #3:

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

input:

50
979124700 -992338349
736374129 734005658
981535490 990865445
-484962537 480422077
-745993272 -748185625
484344794 483931970
-232248914 246030679
-495828121 -497357556
-985814105 -991789434
726694781 730510441
494073302 -491398783
995428232 979904299
749643391 -744013975
248096177 -226384053
-7333...

output:

6

result:

ok single line: '6'

Test #4:

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

input:

46
-199572371 -192785393
989316110 995023728
-789787221 789411221
585957279 -592169437
-582511265 -589750301
-393949582 383032275
-588028366 -591946851
184826022 180434314
998267190 981171313
790204542 -784542306
-988578027 -986833362
-188687082 -183079314
-998815006 -988281872
595132299 -583827520
...

output:

7

result:

ok single line: '7'

Test #5:

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

input:

49
906487856 -953143052
-950934234 -936109651
907154460 975915376
939336319 -914418242
909713554 -911204211
-958765776 -998030591
-959130523 983660999
-942130131 918163279
-926159764 -959435700
-926678580 -951154248
-933502466 -977094402
952097226 922181470
901641247 980225866
-953169715 972540573
-...

output:

12

result:

ok single line: '12'

Test #6:

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

input:

48
243704557 243886225
741847703 742103409
576063232 578812957
-498765984 -494103894
495343325 499055782
495476618 -491751137
409983641 -416089526
-664447792 660953507
-245087552 246165432
-826135529 833057762
581493502 -582519609
327418991 -332503244
80282745 76301615
659700427 -658751059
-41519058...

output:

4

result:

ok single line: '4'

Test #7:

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

input:

44
-994107271 -994905012
991415950 996505441
89845701 -90430171
-363238163 -355859143
-358356759 354953422
-726711842 723711747
-539596442 -541192768
-453177351 -450712641
723241883 -720964778
88096691 81873292
-810047251 -814675705
-994340831 999890026
-180812074 -180764320
-90003513 87174498
45208...

output:

4

result:

ok single line: '4'

Test #8:

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

input:

4
-156549926 -924331297
955370154 119779694
-452637503 -80094304
-187786111 -615328472

output:

3

result:

ok single line: '3'

Test #9:

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

input:

5
-75664414 161433563
821735079 -912616013
-513074987 465623614
-694785438 491460381
806554797 588032912

output:

3

result:

ok single line: '3'

Test #10:

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

input:

6
-641940720 496207435
-124301057 395882339
-550907508 -199725552
-540857797 -159323091
812898562 -619072241
833107948 -452674388

output:

5

result:

ok single line: '5'

Test #11:

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

input:

7
-640171411 -194312902
-841925336 987730324
190043513 -997888031
-818099011 526395621
765098899 -53534033
-519211010 -921903684
749848805 -765518967

output:

6

result:

ok single line: '6'

Test #12:

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

input:

41
380701988 922855772
115265816 624206110
564093844 411574277
-881538381 877200345
-412242344 761745352
945378293 361681623
-904879934 723204845
147880866 -864247586
249024489 -903829852
647589504 -337594157
-518799399 962924076
-850010913 -667767542
163811403 -918456106
-782725002 677956952
223484...

output:

10

result:

ok single line: '10'

Test #13:

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

input:

50
10288942 718800125
-175163671 461348938
-41894187 -188359
361416452 814866862
-483015165 -241162435
688227119 884275048
831652063 485653071
-941435430 716061694
-696492422 292554600
938287584 -761488546
-104687634 -842116647
-569400512 304221855
725171537 257303412
988305163 -45647344
394973454 -...

output:

10

result:

ok single line: '10'

Test #14:

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

input:

34
508290826 15791597
-683720904 -330140838
-811686172 184593566
-887666516 -913521430
-39370660 999925559
-967813073 -855716713
-793030200 640771945
-829134725 -264199529
394959900 -192044348
63343986 42357788
-905654596 376500150
-967662318 158907537
-484425551 624422121
526116315 747079394
-80594...

output:

8

result:

ok single line: '8'

Test #15:

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

input:

49
906143424 417169195
-925069021 40048162
-866308184 -925743164
-957951867 997958323
941169873 880398412
-488065615 -450400835
-288753034 443881249
588383809 -706787880
-952293324 -270851338
-488333825 -210747813
-395352158 91150279
-734516663 -993983984
-263663678 -42897283
-200748493 922344223
47...

output:

7

result:

ok single line: '7'

Test #16:

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

input:

41
75942247 161303090
464585911 600316395
-240652531 482431296
-351550559 361796156
77204917 66670756
204025250 960347706
427356139 667233091
-166970684 562345318
-277739048 442110952
-129868129 602530769
384357399 333625295
-55844442 682324303
353211801 800183789
-92805683 642519265
129835356 88133...

output:

40

result:

ok single line: '40'

Test #17:

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

input:

41
334913690 314675657
570375516 790105979
557755636 525763654
52252985 226231479
278966199 261856430
33026870 337395481
56215814 52477716
446447694 420162673
723567924 684553149
531156355 815327553
30121161 750239361
-46802607 666941363
-110657144 165826886
416329025 895235285
112473551 105073437
1...

output:

31

result:

ok single line: '31'

Test #18:

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

input:

50
11922187 895057064
120652951 156530544
0 0
-489132581 709818172
67494755 842433770
-184220660 313596394
344763311 578941054
40203088 52087198
-112036480 669197362
-323108145 834029658
-40603997 41892396
234121951 684499738
80525837 104385197
-250193124 473233095
320693057 420070901
-44265520 9479...

output:

43

result:

ok single line: '43'

Test #19:

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

input:

41
145091339 853626695
-334823894 333424328
-134733591 133384177
0 0
-268170428 266770009
200691857 176193616
35392433 388720616
10768105 867159573
-284092763 533272989
79691023 154523482
133872430 117454732
-48304426 800569565
400149569 351794686
481979638 646995521
532845451 469578068
219912994 85...

output:

32

result:

ok single line: '32'

Test #20:

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

input:

50
-222291945 779232450
-68568560 349327520
84768797 673756988
369864461 449840862
74862189 147270091
326126660 378112566
-337563402 742106475
166608554 416555061
337416175 467260186
312177887 369572032
27445091 722785664
-266136132 701401452
-122436054 707791201
-47202536 355355692
-98677084 576377...

output:

3

result:

ok single line: '3'

Test #21:

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

input:

50
199759673 522548127
141466143 478564812
-127935176 566933066
-53425330 541884108
155232258 188230107
194814733 548671151
499933623 501042533
-332891006 727412234
101363088 147246160
124979969 655266558
92192035 235440385
-422003444 869427378
-2738584 282258205
1835322 88234069
373493757 509483171...

output:

3

result:

ok single line: '3'

Test #22:

score: -15
Wrong Answer
time: 1ms
memory: 3880kb

input:

50
-745793301 831971251
-281529044 400230556
-685584785 357037077
-860152609 565515261
-1000000000 500575585
-371618700 417831109
-484251935 246978035
-660752788 731212136
-647007878 919784005
-435632943 607374227
-333388972 500093208
-692184601 735913040
-823245814 494037010
-676265223 458097291
-3...

output:

5

result:

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

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

input:

3
498999289 500164826
0 0
-501000711 1000000000

output:

3

result:

ok single line: '3'

Test #98:

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

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

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

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:

Too many queries!!!!@QingyuSecretT0ken123456J0fdj1n2410Bfnf
1724

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

0%