QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#253431 | #800. Triangles | Camillus# | 0 | 0ms | 0kb | C++20 | 2.2kb | 2023-11-16 23:54:14 | 2024-07-04 02:51:36 |
answer
/// @author Camillus <3
#include "bits/stdc++.h"
#ifdef LOCAL
int get_n();
bool is_clockwise(int a, int b, int c);
void give_answer(int s);
#else
# include "trilib.h"
#endif
using namespace std;
random_device rd;
mt19937_64 rnd(rd());
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;
}
}
}
vector<int> D = A;
B.erase(B.begin());
B.pop_back();
D.insert(D.end(), B.begin(), B.end());
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++;
}
}
give_answer(cnt - m);
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: 0
Runtime Error
input:
3 498999289 500164826 0 0 -501000711 1000000000
output:
Unauthorized output
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%