QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#730292 | #9520. Concave Hull | DBsoleil# | WA | 31ms | 3956kb | C++23 | 2.9kb | 2024-11-09 19:34:28 | 2024-11-09 19:34:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
static constexpr int Maxn = 1e5 + 5;
using int_t = int64_t;
using real_t = long double;
struct point {
int_t x, y;
point() { }
point(int_t x, int_t y) : x(x), y(y) { }
friend point operator + (const point &lhs, const point &rhs) { return point(lhs.x + rhs.x, lhs.y + rhs.y); }
friend point operator - (const point &lhs, const point &rhs) { return point(lhs.x - rhs.x, lhs.y - rhs.y); }
friend int_t operator * (const point &lhs, const point &rhs) { return lhs.x * rhs.x + lhs.y * rhs.y; }
int_t abs(void) const { return x * x + y * y; }
friend bool operator < (const point &lhs, const point &rhs) { return lhs.x < rhs.x || (lhs.x == rhs.x && lhs.y < rhs.y); }
}; int_t det(const point &a, const point &b) { return a.x * b.y - a.y * b.x; }
int_t area2(const point &a, const point &b, const point &c) { return abs(det(b - a, c - a)); }
int sgn(int_t x) { return x == 0 ? 0 : (x > 0 ? 1 : -1); }
real_t distance(point p, point x, point y) { return abs((real_t)det(y - x, p - x) / (y - x).abs()); }
bool turn_left(const point &a, const point &b, const point &c)
{ return sgn(det(b - a, c - a)) >= 0; }
vector<point> convex_hull(vector<point> a) {
int n = (int)a.size(), cnt = 0;
if (n < 2) return a;
sort(a.begin(), a.end(), [&](auto lhs, auto rhs)
{ return make_pair(lhs.x, lhs.y) < make_pair(rhs.x, rhs.y); });
vector<point> ret;
for (int i = 0; i < n; ++i) {
while (cnt > 1 && turn_left(ret[cnt - 2], a[i], ret[cnt - 1]))
--cnt, ret.pop_back();
++cnt, ret.push_back(a[i]);
} int fixed = cnt;
for (int i = n - 2; i >= 0; --i) {
while (cnt > fixed && turn_left(ret[cnt - 2], a[i], ret[cnt - 1]))
--cnt, ret.pop_back();
++cnt, ret.push_back(a[i]);
} ret.pop_back(); return ret;
} // convex_hull
int_t calc_area(const vector<point> &a) {
int_t ret = 0;
for (int i = 1; i < (int)a.size() - 1; ++i)
ret += area2(a[0], a[i], a[i + 1]);
return ret;
} // calc_area
int main(void) {
cin.tie(nullptr)->sync_with_stdio(false);
int tests; cin >> tests;
while (tests--) {
int n; cin >> n; vector<point> a(n), c;
for (auto &[x, y]: a) cin >> x >> y;
auto b = convex_hull(a); set<point> sb;
auto area = calc_area(b);
for (auto z: b) sb.insert(z);
for (auto z: a) if (sb.find(z) == sb.end()) c.push_back(z);
if (c.empty()) { cout << "-1\n"; continue; }
auto d = convex_hull(c); int p = 0;
for (int i = 0; i < (int)d.size(); ++i)
if (distance(d[i], b[0], b[1]) < distance(d[p], b[0], b[1])) p = i;
auto tri = area2(d[p], b[0], b[1]);
for (int i = 1, q = p; i < (int)b.size(); ++i) {
point x = b[i], y = b[(i + 1) % (int)b.size()];
while (distance(d[(q + 1) % (int)d.size()], x, y) <= distance(d[q], x, y)) ++q;
tri = min(tri, area2(d[q], x, y));
} cout << area - tri << endl;
}
return 0;
} // main
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
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: 0
Accepted
time: 1ms
memory: 3600kb
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:
2178418010787347715 1826413114144932145 1651687576234220014 1883871859778998985 2119126281997959892 894016174881844630 2271191316922158910 1998643358049669416 1740474221286618711 1168195646932543192
result:
ok 10 lines
Test #3:
score: -100
Wrong Answer
time: 31ms
memory: 3956kb
input:
1000 125 64661186 -13143076 302828013 -185438065 -418713797 -191594241 430218126 -397441626 354327250 -836704374 149668812 -598584998 311305970 66790541 199720625 -592356787 468137 -584752683 258775829 96211747 -358669612 -134890109 -129221188 -998432368 -277309896 -140056561 356901185 420557649 -51...
output:
1986320445246155278 1900093336073022078 1612088392301142476 2012259136539173407 1819942017252118749 1772230185841892196 1164835025329039520 1527446155241140517 1807368432185303666 1236918659444944569 1306839249967484778 1984123720246784099 1868728080720036006 667458140583450322 2127932992585026491 4...
result:
wrong answer 16th lines differ - expected: '447172929227332597', found: '480128762112500892'