QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#253442 | #800. Triangles | Camillus# | 0 | 10ms | 4100kb | C++20 | 3.7kb | 2023-11-17 00:15:49 | 2024-07-04 02:51:44 |
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();
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;
}
详细
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%