QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726397 | #9520. Concave Hull | RWeakest | TL | 1ms | 3628kb | C++17 | 3.7kb | 2024-11-08 23:45:50 | 2024-11-08 23:45:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
ll Test, n, m, k;
struct point {
ll x, y;
point(ll x_ = 0, ll y_ = 0) : x(x_), y(y_) {}
point &operator+=(point p) &{ return x += p.x, y += p.y, *this; }
point &operator+=(ll t) &{ return x += t, y += t, *this; }
point &operator-=(point p) &{ return x -= p.x, y -= p.y, *this; }
point &operator-=(ll t) &{ return x -= t, y -= t, *this; }
point &operator*=(ll t) &{ return x *= t, y *= t, *this; }
point &operator/=(ll t) &{ return x /= t, y /= t, *this; }
friend point operator+(point a, point b) { return a += b; }
friend point operator+(point a, ll b) { return a += b; }
friend point operator-(point a, point b) { return a -= b; }
};
ll cross(point a, point b) {
return a.x * b.y - a.y * b.x;
}
ll cross(point p1, point p2, point p3) {
return cross(p2 - p1, p3 - p2);
}
bool cmp(point a, point b) {
if (a.y != b.y) return a.y < b.y;
return a.x < b.x;
}
point basep;
bool cmpangle(point a, point b) {
if ((a.x - basep.x) * (b.y - basep.y) != (a.y - basep.y) * (b.x - basep.x))
return (a.x - basep.x) * (b.y - basep.y) > (a.y - basep.y) * (b.x - basep.x);
return (abs(a.x - basep.x) + abs(a.y - basep.y) < abs(b.x - basep.x) + abs(b.y - basep.y));
}
vector<point> p, con1, con2;
pair<vector<point>, vector<point> > convex(vector<point> v) {
vector<point> con, res;
if (v.size() <= 2) return make_pair(v, res);
basep = v[0];
for (int i = 1; i < v.size(); i++)
if (v[i].y < basep.y) basep = v[i];
sort(v.begin(), v.end(), cmpangle);
con.push_back(v[0]);
for (int i = 1; i < v.size(); i++) {
while (con.size() > 1 && cross(con[con.size() - 2], con[con.size() - 1], v[i]) < 0) {
res.push_back(con[con.size() - 1]);
con.pop_back();
}
con.push_back(v[i]);
}
// for (int i = 0; i < v.size(); i++) printf("%d: (%lld,%lld)\n", i, v[i].x, v[i].y);
// printf("convex\n");
// for (int i = 0; i < con.size(); i++) printf("%d: (%lld,%lld)\n", i, con[i].x, con[i].y);
// printf("res\n");
// for (int i = 0; i < res.size(); i++) printf("%d: (%lld,%lld)\n", i, res[i].x, res[i].y);
return make_pair(con, res);
}
ll area(point a, point b, point c) {
return abs(cross(a, b, c));
}
ll area(vector<point> v) {
ll res = 0;
for (int i = 1; i < v.size() - 1; i++) {
res += area(v[0], v[i], v[i + 1]);
}
return res;
}
void solve() {
cin >> n;
p.clear(), con1.clear(), con2.clear();
for (int i = 1; i <= n; i++) {
ll x, y;
cin >> x >> y;
p.emplace_back(x, y);
}
pair<vector<point>, vector<point> > result = convex(p);
if (result.first.size() == n) {
cout << "-1\n";
return;
}
con1 = result.first;
p = result.second;
con2 = convex(p).first;
ll sum = area(con1), mini = 4e18;
int j = 0;
for (int i = 0; i < con1.size(); i++) {
point a = con1[i], b = con1[(i + 1) % con1.size()];
while (area(a, b, con2[(j + 1) % con2.size()]) <= area(a, b, con2[j])) {
mini = min(mini, area(a, b, con2[j]));
j = (j + 1) % con2.size();
}
mini = min(mini, area(a, b, con2[j]));
}
cout << sum - mini << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
cin >> Test;
while (Test--) {
solve();
}
return 0;
}
/*
2
6
-2 0
1 -2
5 2
0 4
1 2
3 1
4
0 0
1 0
0 1
1 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
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: 3628kb
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
Time Limit Exceeded
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...