QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#792837 | #9520. Concave Hull | liqingyang# | WA | 22ms | 3660kb | C++17 | 2.2kb | 2024-11-29 14:37:11 | 2024-11-29 14:37:11 |
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 abs((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=1e18;
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: 100
Accepted
time: 0ms
memory: 3660kb
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: 0
Accepted
time: 1ms
memory: 3572kb
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:
2178418010787347715 1826413114144932145 1651687576234220014 1883871859778998985 2119126281997959892 894016174881844630 2271191316922158910 1998643358049669416 1740474221286618711 1168195646932543192
result:
ok 10 lines
Test #3:
score: -100
Wrong Answer
time: 22ms
memory: 3640kb
input:
1000 125 64661186 -13143076 302828013 -185438065 -418713797 -191594241 430218126 -397441626 354327250 -836704374 149668812 -598584998 311305970 66790541 199720625 -592356787 468137 -584752683 258775829 96211747 -358669612 -134890109 -129221188 -998432368 -277309896 -140056561 356901185 420557649 -51...
output:
1986320445246155278 1900093336073022078 1612088392301142476 2012259136539173407 1819942017252118749 1772230185841892196 1164835027347150174 1527446155241140517 1807368432185303666 1236918659444944569 1306839249967484778 1984123720246784099 1868728080720036006 667458140583450322 2127932992585026491 4...
result:
wrong answer 7th lines differ - expected: '1164835025329039520', found: '1164835027347150174'