QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#253437 | #800. Triangles | Camillus# | 0 | 13ms | 4968kb | C++20 | 3.1kb | 2023-11-17 00:11:51 | 2024-07-04 02:51:40 |
Judging History
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();
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;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 15
Accepted
time: 0ms
memory: 3844kb
input:
3 -843737031 -842526876 951189384 673353567 -450418999 301219510
output:
3
result:
ok single line: '3'
Test #2:
score: -15
Wrong Answer
time: 0ms
memory: 4112kb
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:
9
result:
wrong answer 1st lines differ - expected: '4', found: '9'
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: 3968kb
input:
3 498999289 500164826 0 0 -501000711 1000000000
output:
3
result:
ok single line: '3'
Test #98:
score: 0
Accepted
time: 0ms
memory: 3888kb
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: 3752kb
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: 3956kb
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: 3928kb
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: 4200kb
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: 4024kb
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: 11ms
memory: 4676kb
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: 3828kb
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: 4112kb
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: 3824kb
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: 3896kb
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: 3884kb
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: 3892kb
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: 3884kb
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: 4688kb
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: 12ms
memory: 4652kb
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: 4664kb
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: 4688kb
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: 12ms
memory: 4732kb
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: 4928kb
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: 8ms
memory: 4724kb
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: 4732kb
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: 4892kb
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: 12ms
memory: 4792kb
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: 9ms
memory: 4648kb
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: 12ms
memory: 4688kb
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: 12ms
memory: 4768kb
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: 6ms
memory: 4772kb
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: 9ms
memory: 4684kb
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: 8ms
memory: 4728kb
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: 4716kb
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: 4708kb
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: 4680kb
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: 9ms
memory: 4776kb
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: 4968kb
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: 4924kb
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: 4644kb
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%