QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#791945 | #9520. Concave Hull | ticking_away | WA | 1ms | 3880kb | C++20 | 3.5kb | 2024-11-28 22:14:15 | 2024-11-28 22:14:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ui = unsigned int;
using ull = unsigned long long;
using ll = long long;
#define endl '\n'
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int maxn = 2e5 + 10;
const int mod = 1000000007;
#define inl inline
#define fr(i, a, b) for (int i = a; i <= b; i++)
#define ford(i, a, b) for (int i = a; i >= b; i--)
#define forall(i, a) for (auto &i : a)
/**
____ ___ _____
/ ___| _ _ / _ \___ /
\___ \| | | | | | ||_ \
___) | |_| | |_| |__) |
|____/ \__, |\___/____/
|___/
*/
istream &operator>>(istream &in, vector<int> &v)
{
for (auto &i : v)
in >> i;
return in;
}
ostream &operator<<(ostream &out, vector<int> &v)
{
for (auto &i : v)
out << i << " ";
return out;
}
bool _output = 1;
const int EPS = 0;
inline int sign(int a)
{
return a < -EPS ? -1 : a > EPS;
}
inline int cmp(int a, int b)
{
return sign(a - b);
}
#define int ll
struct Point
{
int x, y;
Point() {}
Point(int _x, int _y) : x(_x), y(_y) {}
Point operator-(Point &b)
{
return Point(x - b.x, y - b.y);
}
Point operator+(Point &b)
{
return Point(x + b.x, y + b.y);
}
bool operator<(const Point &b) const
{
return x < b.x || (x == b.x && y < b.y);
}
};
int det(Point a, Point b)
{
return a.x * b.y - a.y * b.x;
}
bool to_left(Point a, Point b, Point c)
{
return det(b - a, c - a) > 0;
}
#define cross(p1, p2, p3) \
((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y))
#define crossOp(p1, p2, p3) sign(cross(p1, p2, p3))
vector<Point> convexHull(vector<Point> ps)
{
int n = ps.size();
if (n <= 2)
return ps;
sort(ps.begin(), ps.end());
vector<Point> qs(n * 2);
int k = 0;
for (int i = 0; i < n; qs[k++] = ps[i++])
while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0)
--k;
for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0)
--k;
qs.resize(k - 1);
return qs;
}
void solve()
{
int n;
cin >> n;
vector<Point> a;
fr(i, 1, n)
{
int x, y;
cin >> x >> y;
a.push_back(Point(x, y));
}
auto c1 = convexHull(a);
set<Point> st;
for (auto i : c1)
{
st.insert(i);
}
vector<Point> b;
for (auto v : a)
{
if (!st.count(v))
{
b.push_back(v);
}
}
// cout << b.size() << endl;
if (b.size() == 0)
{
cout << -1 << endl;
return;
}
auto c2 = convexHull(b);
int sz1 = c1.size(), sz2 = c2.size();
int j = 0;
auto cal = [&](Point &a, Point &b, Point &c)
{
return abs(det(b - a, c - a));
};
int ans = 1e18;
for (int i = 0; i < sz1; i++)
{
while (cal(c1[i], c1[(i + 1) % sz1], c2[j]) > cal(c1[i], c1[(i + 1) % sz1], c2[(j + 1) % sz2]))
{
j = (j + 1) % sz2;
}
ans = min(ans, cal(c1[i], c1[(i + 1) % sz1], c2[j]));
}
int area = 0;
for (int i = 0; i < sz1; i++)
{
area += det(c1[i], c1[(i + 1) % sz1]);
}
ans = area - ans;
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int _ = 1;
if (_output)
cin >> _;
while (_--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
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: 3880kb
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:
202795276562761961 -905211802639263098 253210827344392389 -788416674058499283 -858965342288099898 335194309462221745 16942755278123180 -447935083750505833 -733729900579454325 -183304553600668513
result:
wrong answer 1st lines differ - expected: '2178418010787347715', found: '202795276562761961'