QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#253443 | #800. Triangles | Camillus# | 0 | 0ms | 4080kb | C++20 | 3.7kb | 2023-11-17 00:21:31 | 2024-07-04 02:51:44 |
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(228);
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;
while (true) {
if (is_clockwise(D[l], D[r], D[pr(l)])) {
cnt++;
l--;
} else if (is_clockwise(D[l], D[r], D[nx(r)])) {
cnt++;
r++;
} else {
break;
}
}
r = hullA.size();
l = pr(r);
while (true) {
if (is_clockwise(D[l], D[r], D[pr(l)])) {
cnt++;
l--;
} else if (is_clockwise(D[l], D[r], D[nx(r)])) {
cnt++;
r++;
} else {
break;
}
}
give_answer(m - cnt);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 15
Accepted
time: 0ms
memory: 4080kb
input:
3 -843737031 -842526876 951189384 673353567 -450418999 301219510
output:
3
result:
ok single line: '3'
Test #2:
score: -15
Runtime Error
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:
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: 0
Runtime Error
input:
3 498999289 500164826 0 0 -501000711 1000000000
output:
Unauthorized output
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%