QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#253445 | #800. Triangles | Camillus# | 0 | 7ms | 4764kb | C++20 | 3.9kb | 2023-11-17 00:26:31 | 2024-07-04 02:51:46 |
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(6);
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();
l = pr(r);
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;
}
}
give_answer(m - Q.size());
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
3 -843737031 -842526876 951189384 673353567 -450418999 301219510
output:
Unauthorized output
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Runtime Error
Test #97:
score: 20
Accepted
time: 1ms
memory: 3780kb
input:
3 498999289 500164826 0 0 -501000711 1000000000
output:
3
result:
ok single line: '3'
Test #98:
score: 0
Accepted
time: 1ms
memory: 3836kb
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: 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: 3980kb
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: 3816kb
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: 4084kb
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: 7ms
memory: 4764kb
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: 4092kb
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: 4128kb
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: 4116kb
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: 3804kb
input:
6 154336691 188058821 1000000000 666141970 501648357 332968552 0 0 667499672 1000000000 334145828 500727904
output:
5
result:
ok single line: '5'
Test #109:
score: -20
Runtime Error
input:
6 498734119 1000000000 -251037445 332876405 -501265881 665829221 250154255 500184857 -69341346 663798009 0 0
output:
Unauthorized output
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%