QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726509 | #9520. Concave Hull | ExtractStars | WA | 1ms | 3808kb | C++17 | 3.6kb | 2024-11-09 01:53:36 | 2024-11-09 01:53:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
struct Point
{
ll x, y;
bool operator<(const Point &rhs) const
{
return (x < rhs.x) || (x == rhs.x && y < rhs.y);
}
};
ll cross(const Point &O, const Point &A, const Point &B)
{
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
vector<Point> convexHull(vector<Point> &pts)
{
int n = pts.size();
sort(pts.begin(), pts.end());
vector<Point> hull;
for (int i = 0; i < n; ++i)
{
while (hull.size() >= 2 && cross(hull[hull.size() - 2], hull[hull.size() - 1], pts[i]) <= 0)
{
hull.pop_back();
}
hull.push_back(pts[i]);
}
int t = hull.size() + 1;
for (int i = n - 2; i >= 0; --i)
{
while (hull.size() >= t && cross(hull[hull.size() - 2], hull[hull.size() - 1], pts[i]) <= 0)
{
hull.pop_back();
}
hull.push_back(pts[i]);
}
hull.pop_back();
return hull;
}
ll area2(const vector<Point> &p)
{
ll area2 = 0;
int n = p.size();
for (int i = 0; i < n; ++i)
{
int j = (i + 1) % n;
area2 += (p[i].x * p[j].y) - (p[j].x * p[i].y);
}
return abs(area2);
}
ll dis2(const Point &a, const Point &b)
{
ll dx = a.x - b.x;
ll dy = a.y - b.y;
return dx * dx + dy * dy;
}
void solve()
{
int n;
cin >> n;
vector<Point> P(n);
for (int i = 0; i < n; ++i)
{
cin >> P[i].x >> P[i].y;
}
vector<Point> poly = convexHull(P);
int num = poly.size();
if (num == n)
{
cout << "-1\n";
return;
}
ll S = area2(poly);
vector<pair<ll, ll>> temp;
for (auto &p : poly)
{
temp.emplace_back(p.x, p.y);
}
sort(temp.begin(), temp.end());
vector<Point> waitP;
for (int i = 0; i < n; ++i)
{
pair<ll, ll> t = {P[i].x, P[i].y};
if (!binary_search(temp.begin(), temp.end(), t))
{
waitP.push_back(P[i]);
}
}
if (waitP.empty())
{
cout << "1\n";
return;
}
ll tot = 0;
for (int i = 0; i < num; ++i)
{
int j = (i + 1) % num;
tot += (poly[i].x * poly[j].y) - (poly[j].x * poly[i].y);
}
if (tot < 0)
{
reverse(poly.begin(), poly.end());
}
auto area = [&](const Point &a, const Point &b, const Point &x) -> ll
{
ll s = (b.x - a.x) * (x.y - a.y) - (b.y - a.y) * (x.x - a.x);
return abs(s);
};
ll mn = 1e18;
for (auto &x : waitP)
{
int l = 0;
int r = num - 1;
while (r - l > 4)
{
int m1 = l + (r - l) / 3;
int m2 = r - (r - l) / 3;
ll cross1 = area(poly[m1], poly[(m1 + 1) % num], x);
ll cross2 = area(poly[m2], poly[(m2 + 1) % num], x);
if (cross1 < cross2)
r = m2;
else
l = m1;
}
ll temp = 1e18;
for (int i = l; i <= r; ++i)
{
ll cur = area(poly[i], poly[(i + 1) % num], x);
if (cur < temp)
temp = cur;
}
if (temp < mn)
mn = temp;
}
ll ans = S - mn;
if (ans > 0)
cout << ans << "\n";
else
cout << "-1\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int _;
cin >> _;
while (_--)
{
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3808kb
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: 3640kb
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:
2178410906926518141 1826413114144932145 1651687576234220014 1883871859778998985 2117861879018439740 894016174881844630 2271174337159857750 1998643358049669416 1727300161677395529 1168195646932543192
result:
wrong answer 1st lines differ - expected: '2178418010787347715', found: '2178410906926518141'