QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#722450 | #9520. Concave Hull | Lcyanstars | WA | 1ms | 4084kb | C++14 | 2.4kb | 2024-11-07 19:05:07 | 2024-11-07 19:05:07 |
Judging History
answer
#include <bits/stdc++.h>
//jiangly, modified
using i64 = long long; // long long, double
const i64 eps=0; //0, 1e-9
struct Point {
i64 x;
i64 y;
Point(i64 x = 0, i64 y = 0) : x(x), y(y) {}
bool operator <(const Point& a) const
{
return x == a.x ?y<a.y:x<a.x;
}
};
Point operator+(const Point &a, const Point &b) {
return Point(a.x + b.x, a.y + b.y);
}
Point operator-(const Point &a, const Point &b) {
return Point(a.x - b.x, a.y - b.y);
}
i64 dot(const Point &a, const Point &b) {
return a.x * b.x + a.y * b.y;
}
i64 cross(const Point &a, const Point &b) {
return a.x * b.y - a.y * b.x;
}
i64 area(const Point &a, const Point& b, const Point& c) {
return cross(a - b, b - c); // 有向面积,正代表 b-c 在 a-b 左侧
}
std::map<Point,bool> vis;
std::vector<Point> getHull(std::vector<Point>& p) {
std::vector<Point> h, l;
std::sort(p.begin(), p.end());
if (p.size() <= 1) {
return p;
}
for (auto a : p) {
while (h.size() > 1 && cross(a - h.back(), a - h[h.size() - 2]) <= eps) {
h.pop_back();
}
while (l.size() > 1 && cross(a - l.back(), a - l[l.size() - 2]) >= -eps) {
l.pop_back();
}
l.push_back(a);
h.push_back(a);
}
l.pop_back();
std::reverse(h.begin(), h.end());
h.pop_back();
l.insert(l.end(), h.begin(), h.end());
for(auto p:l)
vis[p]=true;
return l;
}
int main()
{
int _;
for(scanf("%d",&_);_;_--)
{
vis.clear();
int n;
scanf("%d",&n);
std::vector<Point> P(n);
for(int i=0;i<n;i++)
scanf("%lld%lld",&P[i].x,&P[i].y);
auto con=getHull(P);
std::vector<Point> nP;
for(auto a:P)
if(!vis[a])
nP.push_back(a);
auto ncon=getHull(nP);
int N=(int)con.size(),M=(int)ncon.size();
if(M == 0)
{
printf("-1\n");
continue;
}
i64 ar=0;
for(int i=0;i<N;i++)
ar += area(con[i],con[(i+1)%N],con[(i+2)%N]);
ar /= 2;
i64 mn=ar;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
mn=std::min(area(con[i],con[(i+1)%N],ncon[j]),mn);
printf("%lld\n",ar-mn);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4084kb
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: 3832kb
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:
436901472928748124 142985787925747604 6716882489433884 462692168984313134 592769233092856550 450587273009334171 364753001879370583 316129459382945126 750838921404253650 61161851159402348
result:
wrong answer 1st lines differ - expected: '2178418010787347715', found: '436901472928748124'