QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#736107 | #9520. Concave Hull | PHarr | WA | 1ms | 3604kb | C++20 | 3.0kb | 2024-11-12 00:45:28 | 2024-11-12 00:45:30 |
Judging History
answer
#include <bits/stdc++.h>
using i32 = int32_t;
using i64 = long long;
#define int i64
const int inf = LLONG_MAX / 2;
struct Point {
i64 x, y;
Point(i64 x = 0, i64 y = 0) : x(x), y(y) {};
};
using Vec = Point;
using Points = std::vector<Point>;
Vec operator-(Vec u, Vec v) { return Vec(u.x - v.x, u.y - v.y); }
int operator^(Vec u, Vec v) { return u.x * v.y - u.y * v.x; }
bool operator<(Point A, Point B) {
if (A.x != B.x) return A.x < B.x;
return A.y < B.y;
}
bool check(Point p, Point q, Point r) {
return 0 < ((q - p) ^ (r - q));
}
std::pair<Points, Points> chull(Points &ps) {
std::sort(ps.begin(), ps.end());
std::vector<int> I{0}, used(ps.size());
for (int i = 1; i < ps.size(); i++) { // 下凸包
while (I.size() > 1 and !check(ps[I[I.size() - 2]], ps[I.back()], ps[i]))
used[I.back()] = 0, I.pop_back();
used[i] = 1, I.push_back(i);
}
for (int i = ps.size() - 2, tmp = I.size(); i >= 0; i--) { // 上凸包
if (used[i]) continue;
while (I.size() > tmp and !check(ps[I[I.size() - 2]], ps[I.back()], ps[i]))
used[I.back()] = 0, I.pop_back();
used[i] = 1, I.push_back(i);
}
Points H;
I.pop_back();
for (auto i: I)
H.push_back(ps[i]);
Points notH;
for (int i = 1; i < ps.size(); i++) {
if (used[i]) continue;
notH.push_back(ps[i]);
}
return std::pair(H, notH);
}
int area(Point a, Point b, Point c) {
return std::abs((b - a) ^ (c - a));
}
void solve() {
int n;
std::cin >> n;
Points ps(n);
for (auto &[x, y]: ps)
std::cin >> x >> y;
auto [c1, new_ps] = chull(ps);
ps = move(new_ps);
int chull_area = 0;
for (int i = 0; i < c1.size(); i++)
chull_area += c1[i] ^ c1[(i + 1) % c1.size()];
if (ps.empty()) {
std::cout << -1 << "\n";
} else if (ps.size() < 3) {
int ret = inf;
for (int i = 0; i < ps.size(); i++)
for (int j = 0; j < c1.size(); j++)
ret = std::min(ret, area(ps[i], c1[j], c1[(j + 1) % c1.size()]));
std::cout << chull_area - ret << "\n";
} else {
auto [c2, _] = chull(ps);
int it = 0, val = area(c2[0], c1[0], c1[1]);
for (int i = 1, x; i < c1.size(); i++) {
x = area(c2[0], c1[i], c1[(i + 1) % c1.size()]);
if (x < val) val = x, it = i;
}
int ret = val;
for (int i = 1; i < c2.size(); i++) {
val = area(c2[i], c1[it], c1[(it + 1) % c1.size()]);
for (int x; true; it = (it + 1) % c1.size()) {
x = area(c2[i], c1[(it + 1) % c1.size()], c1[(it + 2) % c1.size()]);
if (x >= val) break;
val = x;
}
ret = std::min(ret, val);
}
std::cout << chull_area - ret << "\n";
}
return;
}
i32 main() {
i32 T;
std::cin >> T;
while (T--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3604kb
input:
2 6 -2 0 1 -2 5 2 0 4 1 2 3 1 4 0 0 1 0 0 1 1 1
output:
40 -1
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3580kb
input:
10 243 -494423502 -591557038 -493438474 -648991734 -493289308 -656152126 -491185085 -661710614 -489063449 -666925265 -464265894 -709944049 -447472922 -737242534 -415977509 -773788538 -394263365 -797285016 -382728841 -807396819 -373481975 -814685302 -368242265 -818267002 -344482838 -833805545 -279398...
output:
2178414095795486749 1825079923389352515 1650158198749955336 1883485336300243169 2119126281997959892 892733130592920715 2271174337159857750 1998643358049669416 1740474221286618711 1167480950136890085
result:
wrong answer 1st lines differ - expected: '2178418010787347715', found: '2178414095795486749'