QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#745983 | #9520. Concave Hull | P-Bao | WA | 1ms | 4160kb | C++20 | 3.3kb | 2024-11-14 12:47:38 | 2024-11-14 12:47:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
struct Point
{
ll x, y;
double angle;
bool operator<(Point p)
{
return x < p.x || (x == p.x && y < p.y);
}
};
ll cross_product(Point O, Point A, Point B)
{
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
Point find_center(const std::vector<Point> &points)
{
double center_x = 0, center_y = 0;
for (const auto &point : points)
{
center_x += point.x;
center_y += point.y;
}
center_x /= points.size();
center_y /= points.size();
return {center_x, center_y, 0};
}
double calculate_angle(const Point& point, const Point& center) { return atan2(point.y - center.y, point.x - center.x); }
vector<pair<Point, int>> convex_hull(vector<Point>& A)
{
//for(Point P : A) cout << P.x << " " << P.y << endl;
int n = A.size(), k = 0;
if (n <= 3)
{
vector<pair<Point, int>> res;
for (int i = 0; i < n; ++i)
res.push_back({A[i], i});
}
vector<pair<Point, int>> ans(2 * n);
//sort(A.begin(), A.end());
for (int i = 0; i < n; ++i)
{
while (k >= 2 && cross_product(ans[k - 2].first, ans[k - 1].first, A[i]) <= 0)
k--;
ans[k++] = {A[i], i};
}
for (size_t i = n - 1, t = k + 1; i > 0; --i)
{
while (k >= t && cross_product(ans[k - 2].first, ans[k - 1].first, A[i - 1]) <= 0)
k--;
ans[k++] = {A[i - 1], i - 1};
}
ans.resize(k - 1);
return ans;
}
ll polygonArea(const vector<pair<Point, int>> &points)
{
int n = points.size();
ll area = 0;
for (int i = 0; i < n; i++)
{
int j = (i + 1) % n;
area += points[i].first.x * points[j].first.y;
area -= points[j].first.x * points[i].first.y;
}
return area;
}
ll polygonArea(const vector<Point> &points)
{
int n = points.size();
ll area = 0;
for (int i = 0; i < n; i++)
{
int j = (i + 1) % n;
area += points[i].x * points[j].y;
area -= points[j].x * points[i].y;
}
return area;
}
void solve()
{
int n;
cin >> n;
vector<Point> p(n);
for (int i = 0; i < n; ++i)
cin >> p[i].x >> p[i].y;
Point center = find_center(p);
for (auto& point : p) { point.angle = calculate_angle(point, center); }
sort(p.begin(), p.end(), [](const Point& a, const Point& b) { return a.angle < b.angle;});
//for(Point P : p) cout << P.x << " " << P.y << endl;
vector<pair<Point, int>> hull = convex_hull(p);
int m = hull.size();
if (m == n)
{
cout << -1 << endl;
return;
}
ll mx = LLONG_MAX;
for(int i = 0; i < m; ++i){
int nxt = (i + 1) % m;
ll cur = LLONG_MAX;
for(int j = hull[i].second + 1; j < hull[nxt].second; ++j){
//cout << p[j].x << " " << p[j].y << endl;
cur = min(cur, polygonArea({hull[nxt].first, p[j], hull[i].first}));
}
mx = min(mx, cur);
}
//cout << mx << endl;
cout << polygonArea(hull) - mx << endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
while(t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4144kb
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: 4160kb
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:
2194049972500610844 1755080791391459355 1596473932092598436 1916501849663426922 2129943229584798024 851569805537003463 2265141682941303722 1943240185850515424 1519613012354149392 1108633123320911092
result:
wrong answer 1st lines differ - expected: '2178418010787347715', found: '2194049972500610844'