QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#253441 | #800. Triangles | Camillus# | 0 | 28ms | 4396kb | C++20 | 3.5kb | 2023-11-17 00:15:19 | 2024-07-04 02:51:43 |
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()}));
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 15
Accepted
time: 1ms
memory: 3864kb
input:
3 -843737031 -842526876 951189384 673353567 -450418999 301219510
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3796kb
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: 3816kb
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: 0ms
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: 1ms
memory: 3888kb
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: 3960kb
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: -15
Wrong Answer
time: 1ms
memory: 3860kb
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:
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: 1ms
memory: 3892kb
input:
3 498999289 500164826 0 0 -501000711 1000000000
output:
3
result:
ok single line: '3'
Test #98:
score: 0
Accepted
time: 1ms
memory: 4100kb
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: 3912kb
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: 6ms
memory: 3932kb
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: 4ms
memory: 3852kb
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: -20
Wrong Answer
time: 28ms
memory: 4396kb
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:
Too many queries!!!!@QingyuSecretT0ken123456J0fdj1n2410Bfnf 7604
result:
wrong answer 1st lines differ - expected: '7604', found: 'Too many queries!!!!@QingyuSecretT0ken123456J0fdj1n2410Bfnf'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%