QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#730476 | #9520. Concave Hull | silver_muse | WA | 1ms | 7732kb | C++20 | 2.8kb | 2024-11-09 20:23:07 | 2024-11-09 20:23:07 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define ph push_back
#define pp pop_back
using namespace std;
typedef int db;
// const double eps=1e-8;
// int sgn(db x)
// {
// if(fabs(x)<eps) return 0;
// else return x<0?-1:1;
// }
struct Point
{
db x,y;
Point(){}
Point(db x,db 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 ==(Point B){ return x-B.x==0&&y-B.y==0; }
bool operator <(Point B)
{
return (x-B.x<0)||(x-B.x==0&&y-B.y<0);
}
};
bool operator <(const Point &A,const Point &B)
{
return (A.x-B.x<0)||(A.x-B.x==0&&A.y-B.y<0);
}
typedef Point Vector;
double cross(Vector A,Vector B){ return A.x*B.y-A.y*B.x; }
double dist(Point A,Point B){ return hypot(A.x-B.x,A.y-B.y); }
int convexhull(Point *p,int n,Point *ch)
{
sort(p,p+n);
int v=0;
for(int i=0;i<n;i++)
{
while(v>1&&cross(ch[v-1]-ch[v-2],p[i]-ch[v-1])<=0) v--;
ch[v++]=p[i];
}
int j=v;
for(int i=n-2;i>=0;i--)
{
while(v>j&&cross(ch[v-1]-ch[v-2],p[i]-ch[v-1])<=0) v--;
ch[v++]=p[i];
}
if(n>1) v--;
return v;
}
int area(Point a,Point b,Point c)
{
return abs(cross(b-a,c-a));
}
const int N=1e5+5,inf=1e18;
int T,n;
Point p[N],pi[N],cho[N],chi[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>T;
while(T--)
{
cin>>n;
for(int i=0;i<n;i++) cin>>p[i].x>>p[i].y;
int cnto=convexhull(p,n,cho);
map<Point,bool>mp;
for(int i=0;i<cnto;i++) mp[cho[i]]=1;
int ni=0;
for(int i=0;i<n;i++)
if(!mp[p[i]]) pi[ni++]=p[i];
if(!ni) { cout<<-1<<endl; continue; }
int res=0,mn=inf;
for(int i=0;i<cnto;i++) res+=area(cho[i],cho[(i+1)%cnto],pi[0]);
if(ni<3)
{
for(int i=0;i<cnto;i++)
{
Point u=cho[i],v=cho[(i+1)%cnto];
for(int j=0;j<ni;j++)
mn=min(mn,area(u,v,pi[j]));
}
}
else
{
int cnti=convexhull(pi,ni,chi);
int t;
for(int i=0;i<cnti;i++)
if(area(cho[0],cho[1],chi[i])<area(cho[0],cho[1],chi[(i+1)%cnti]))
{
t=i;
break;
}
for(int i=0;i<cnto;i++)
{
Point u=cho[i],v=cho[(i+1)%cnto];
while(area(u,v,chi[t])>=area(u,v,chi[(t+1)%cnti])) t=(t+1)%cnti;
mn=min(mn,area(cho[0],cho[1],chi[t]));
}
}
cout<<res-mn<<endl;
}
return 0;
}
/*
2
6
-2 0
1 -2
5 2
0 4
1 2
3 1
4
0 0
1 0
0 1
1 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7708kb
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: 7732kb
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:
2168815737458626770 1819399810238262539 1637125363301102190 1707641623366362000 2109987278957150826 857250288992759368 2264412806401412347 1993716701092309232 1714016191330242194 1159871166840430278
result:
wrong answer 1st lines differ - expected: '2178418010787347715', found: '2168815737458626770'