QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#253447 | #800. Triangles | Camillus# | 0 | 13ms | 5052kb | C++20 | 4.0kb | 2023-11-17 00:30:28 | 2024-07-04 02:51:46 |
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;
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%