QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#579051 | #8550. All the Way Left | thinking (Fedor Romashov, Alexey Mikhnenko, Gimran Abdullin) | WA | 1ms | 3556kb | C++20 | 2.5kb | 2024-09-21 06:11:00 | 2024-09-21 06:11:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define all(a) begin(a), end(a)
#define len(a) int((a).size())
struct point {
ll x, y;
ll length() const {
return x * x + y * y;
}
point operator-(const point &other) const {
return {x - other.x, y - other.y};
}
ll operator%(const point &other) const {
return x * other.y - y * other.x;
}
int side() const {
return make_pair(x, y) < make_pair(0ll, 0ll);
}
};
void solve(int /* test_num */) {
int n;
cin >> n;
vector<point> a(n);
for (auto &[x, y] : a) {
cin >> x >> y;
}
if (n <= 2) {
cout << n << '\n';
return;
}
bool on_line = true;
for (int i = 2; i < n; i++) {
on_line &= (a[i] - a[0]) % (a[1] - a[0]) == 0;
}
if (on_line) {
cout << "2\n";
return;
}
for (int i = 1; i < n; i++) {
if (make_pair(a[i].x, a[i].y) < make_pair(a[0].x, a[0].y)) {
swap(a[i], a[0]);
}
}
sort(1 + all(a), [&](point p, point q) {
p = p - a[0];
q = q - a[0];
ll prod = p % q;
if (prod != 0) {
return prod > 0;
}
return p.length() < q.length();
});
vector<point> hull = {a[0], a[1]}, rem;
for (int i = 2; i < n; i++) {
while ((hull.back() - hull[len(hull) - 2]) % (a[i] - hull.back()) < 0) {
rem.push_back(hull.back());
hull.pop_back();
}
hull.push_back(a[i]);
}
int ans = len(hull);
for (auto c : a) {
vector<point> v;
for (auto p : rem) {
if (p.x != c.x || p.y != c.y) {
v.push_back(p - c);
}
}
if (v.empty()) {
continue;
}
auto compare = [&](point p, point q) {
if (p.side() != q.side()) {
return p.side() < q.side();
}
return p % q < 0;
};
sort(all(v), compare);
int tot = 1;
ans++;
for (int i = 0; i + 1 < len(v); i++) {
if (compare(v[i], v[i + 1])) {
tot++;
ans++;
}
}
}
cout << ans << '\n';
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tests;
cin >> tests;
for (int test_num = 1; test_num <= tests; test_num++) {
solve(test_num);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3488kb
input:
3 4 1 1 3 1 2 2 2 3 3 1 1 1 2 1 3 6 1 1 2 1 2 2 2 3 3 2 4 2
output:
6 2 13
result:
ok 3 number(s): "6 2 13"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3556kb
input:
15 1 1 1 2 1 1 1 2 3 1 1 1 2 1 3 3 1 1 1 2 2 2 5 1 1 1 3 2 2 3 1 3 3 6 1 1 1 3 2 2 3 2 4 1 4 3 6 1 3 2 1 2 2 2 3 2 4 3 2 6 1 1 5 1 3 5 2 2 4 2 3 3 7 1 1 5 1 2 2 3 2 4 2 3 3 3 4 6 2 10 8 9 2 3 2 5 3 5 2 6 10 1 10 7 6 8 4 3 8 6 9 3 7 6 8 8 5 10 9 8 8 8 1 1 2 3 2 4 1 6 5 3 5 4 6 1 6 6 8 1 1 2 3 3 3 4 2...
output:
1 2 2 3 8 14 12 16 22 16 54 32 28 10 14
result:
wrong answer 10th numbers differ - expected: '10', found: '16'