QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#792871 | #9520. Concave Hull | liqingyang# | WA | 0ms | 3832kb | C++17 | 2.2kb | 2024-11-29 14:49:00 | 2024-11-29 14:49:05 |
Judging History
answer
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct point
{
int x,y;
};
inline bool operator <(const point &a,const point &b)
{
return a.x==b.x?a.y<b.y:a.x<b.x;
}
inline point operator -(const point &a,const point &b)
{
return {a.x-b.x,a.y-b.y};
}
inline long long operator *(const point &a,const point &b)
{
return (long long)a.x*b.y-(long long)a.y*b.x;
}
int T,n,head,sta[100010];
point a[100010];
bool mark[100010];
inline long long calc(int x,int y,int z)
{
return (a[y]-a[x])*(a[z]-a[x]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;
mark[i]=0;
}
sort(a+1,a+n+1);
vector<int> v,V;
sta[head=1]=1;
for(int i=2;i<=n;i++)
{
while(head>1&&(a[sta[head]]-a[sta[head-1]])*
(a[i]-a[sta[head-1]])>0)
{
head--;
}
sta[++head]=i;
}
for(int i=1;i<=head;i++)
{
v.emplace_back(sta[i]);
mark[sta[i]]=1;
}
sta[head=1]=n;
for(int i=n-1;i;i--)
{
while(head>1&&(a[sta[head]]-a[sta[head-1]])*
(a[i]-a[sta[head-1]])>0)
{
head--;
}
sta[++head]=i;
}
for(int i=2;i<head;i++)
{
v.emplace_back(sta[i]);
mark[sta[i]]=1;
}
if(v.size()==n)
{
cout<<-1<<endl;
continue;
}
head=0;
for(int i=1;i<=n;i++)
{
if(mark[i])
{
continue;
}
while(head>1&&(a[sta[head]]-a[sta[head-1]])*
(a[i]-a[sta[head-1]])>0)
{
head--;
}
sta[++head]=i;
}
for(int i=1;i<=head;i++)
{
V.emplace_back(sta[i]);
}
head=0;
for(int i=n;i;i--)
{
if(mark[i])
{
continue;
}
while(head>1&&(a[sta[head]]-a[sta[head-1]])*
(a[i]-a[sta[head-1]])>0)
{
head--;
}
sta[++head]=i;
}
for(int i=2;i<head;i++)
{
V.emplace_back(sta[i]);
}
long long ans=9e18;
for(int i=0,j=0;i<v.size();i++)
{
while(calc(v[i],v[(i+1)%v.size()],V[j])>
calc(v[i],v[(i+1)%v.size()],V[(j+1)%V.size()]))
{
j=(j+1)%V.size();
}
ans=min(ans,-calc(v[i],v[(i+1)%v.size()],V[j]));
}
ans*=-1;
for(int i=0;i<v.size();i++)
{
ans-=calc(0,v[i],
v[(i+1)%v.size()]);
}
cout<<ans<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3832kb
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:
35 -1
result:
wrong answer 1st lines differ - expected: '40', found: '35'