QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#743570 | #9520. Concave Hull | gjlccc | WA | 1ms | 3600kb | C++20 | 3.2kb | 2024-11-13 19:31:52 | 2024-11-13 19:31:53 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
int n, m;
struct Point {
int x, y, idx;
bool operator<(const Point &b) const { return x == b.x ? y < b.y : x < b.x; }
friend Point operator-(Point a, Point b) { return {a.x - b.x, a.y - b.y}; }
};
ll vis[N];
ll cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
ll cross(Point a, Point b, Point c) { return cross(b - a, c - a); }
ll dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
// Point operator-(Point a, Point b) { return {a.x - b.x, a.y - b.y}; }
// Point operator+(Point a, Point b) { return {a.x + b.x, a.y + b.y}; }
// Point operator*(Point a, ll b) { return {a.x * b, a.y * b}; }
// Point operator/(Point a, ll b) { return {a.x / b, a.y / b}; }
// ll dis(Point a) { return a.x * a.x + a.y * a.y; }
// ll dis(Point a, Point b) { return dis(a - b); }
vector<Point> a1, con1, con2, a2;
vector<Point> get_hull(vector<Point> &a) {
ll n = a.size();
if (n <= 2) {
return a;
}
vector<Point> ans(n * 2);
sort(a.begin(), a.end());
int now = -1;
for (ll i = 0; i < n; i++) {
while (now > 0 && cross(a[i], ans[now], ans[now - 1]) <= 0) {
now--;
}
ans[++now] = a[i];
}
int pre = now;
for (ll i = n - 2; i >= 0; i--) {
while (now > pre && cross(a[i], ans[now], ans[now - 1]) <= 0) {
now--;
}
ans[++now] = a[i];
}
ans.resize(now);
return ans;
}
void solve() {
ll n;
a1.clear();
a2.clear();
con1.clear();
con2.clear();
cin >> n;
for (ll i = 1; i <= n; i++) vis[i] = 0;
for (ll i = 1; i <= n; i++) {
ll x, y;
cin >> x >> y;
a1.emplace_back((Point){x, y, i});
// cout << a1[i - 1].x << " " << a1[i - 1].y << " " << a1[i - 1].idx <<
// endl;
}
// sort(a1.begin(), a1.end());
con1 = get_hull(a1);
for (auto aaa : con1) {
vis[aaa.idx] = 1;
}
if (con1.size() == n) {
cout << -1 << "\n";
return;
}
for (auto aaa : a1) {
if (vis[aaa.idx] == 0) {
a2.push_back(aaa);
}
}
reverse(con1.begin(), con1.end());
con2 = get_hull(a2);
reverse(con2.begin(), con2.end());
ll ans = 0;
ll l = 0, r = 0;
ll len1 = con1.size();
ll len2 = con2.size();
for (ll i = 0; i < len1; i++) {
ans = ans + cross(con1[i], con1[(i + 1) % len1]);
}
// for (auto aaa : con1) {
// cout << aaa.x << " " << aaa.y << endl;
// }
// cout << "\n";
// for (auto aaa : con2) {
// cout << aaa.x << " " << aaa.y << endl;
// }
ans = abs(ans);
ll tmp = 1e18;
// cout << abs(cross(con1[0], con1[1], con2[1])) << endl;
for (ll i = 0; i < len1; i++) {
while (cross(con1[i], con1[(i + 1) % len1], con2[(r + 1) % len2]) <
cross(con1[i], con1[(i + 1) % len1], con2[r])) {
r = (r + 1) % len2;
}
// cout << abs(get_thr_p_area(con1[i], con1[(i + 1) % len1], con2[r])) <<
// endl;
tmp = min(tmp, abs(cross(con1[i], con1[(i + 1) % len1], con2[r])));
// cout << tmp << endl;
}
cout << ans - tmp << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t = 1;
cin >> t;
while (t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3508kb
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: 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:
10337402351 1736537664 2024061003 6498155794 8955700191 2255545308 131733416 4850012323 -795159809 943828458
result:
wrong answer 1st lines differ - expected: '2178418010787347715', found: '10337402351'