QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#736449 | #9520. Concave Hull | xsdgp | WA | 1ms | 3908kb | C++20 | 2.5kb | 2024-11-12 11:09:48 | 2024-11-12 11:09:57 |
Judging History
answer
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n,m;
struct VECTOR
{
double x,y;
double operator^(const VECTOR &v)const
{
return x*v.y-y*v.x;
}
};
struct POINT
{
double x,y;
bool operator<(const POINT &p)const
{
if(x==p.x)return y<p.y;
else return x<p.x;
}
bool operator==(const POINT &p)const
{
return x==p.x&&y==p.y;
}
VECTOR operator-(const POINT &p)const
{
return {x-p.x,y-p.y};
}
}p[100005],p1[100005];
int cross(VECTOR v1,VECTOR v2)
{
return v1^v2;
}
vector<POINT> st,st1;
map<POINT,bool> mp;
bool check(POINT p)
{
POINT back1=st.back(),back2=*(st.rbegin()+1);
return cross(back1-back2,p-back1)<=0;
}
void andrew()
{
st.clear();
sort(p+1,p+n+1);
for(int i=1;i<=n;i++)
{
while(st.size()>1&&check(p[i]))st.pop_back();
st.push_back(p[i]);
}
int k=st.size();
for(int i=n-1;i>=1;i--)
{
while(st.size()>k&&check(p[i]))st.pop_back();
st.push_back(p[i]);
}
st.pop_back();
}
bool check1(POINT p)
{
POINT back1=st1.back(),back2=*(st1.rbegin()+1);
return cross(back1-back2,p-back1)<=0;
}
void andrew1()
{
st1.clear();
sort(p1+1,p1+m+1);
for(int i=1;i<=m;i++)
{
while(st1.size()>1&&check1(p1[i]))st1.pop_back();
st1.push_back(p1[i]);
}
int k=st1.size();
for(int i=m-1;i>=1;i--)
{
while(st1.size()>k&&check1(p1[i]))st1.pop_back();
st1.push_back(p1[i]);
}
st1.pop_back();
}
int rotcaliper()
{
int j=0,sub=1e18;
VECTOR v=st[1]-st[0];
while(m!=1&&cross(v,st1[(j+1)%st1.size()]-st[0])<=cross(v,st1[j]-st[0]))j=(j+1)%st1.size();
while(m!=1&&cross(v,st1[(j-1+st1.size())%st1.size()]-st[0])<=cross(v,st1[j]-st[0]))j=(j-1+st1.size())%st1.size();
for(int i=0;i<st.size();i++)
{
int i1=(i+1)%st.size();
VECTOR v=st[i1]-st[i];
while(m!=1&&cross(v,st1[(j+1)%st1.size()]-st[i])<=cross(v,st1[j]-st[i]))j=(j+1)%st1.size();
sub=min(sub,cross(v,st1[j]-st[i]));
}
return sub;
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>p[i].x>>p[i].y;
andrew();
int sum=0;
for(int i=0;i<st.size();i++)
{
mp[st[i]]=1;
POINT o={0,0};
sum+=cross(st[i]-o,st[(i+1)%st.size()]-o);
}
m=0;
for(int i=1;i<=n;i++)
if(mp.find(p[i])==mp.end())p1[++m]=p[i];
andrew1();
if(m==0)cout<<-1<<endl;
else cout<<sum-rotcaliper()<<endl;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--)solve();
return 0;
}
/*
3
6
-2 0
1 -2
5 2
0 4
1 2
3 1
4
0 0
1 0
0 1
1 1
5
-2 0
1 -2
5 2
0 4
3 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3856kb
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: 3908kb
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:
2178418010787347730 1826413114144932218 1651687576234220015 1883871859778998916 2119126281997959816 894016174881844663 2271191316922159135 1998643358049669502 1740474221286618592 1168195646932543204
result:
wrong answer 1st lines differ - expected: '2178418010787347715', found: '2178418010787347730'