QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#748464 | #9520. Concave Hull | Lynia | WA | 1ms | 7936kb | C++23 | 3.6kb | 2024-11-14 20:28:29 | 2024-11-14 20:28:29 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
int len=0;
char ibuf[(1<<21)+1],*iS,*iT,out[(1<<25)+1];
#if ONLINE_JUDGE
#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
#else
#define gh() getchar()
#endif
#define reg register
inline int read(){
reg char ch=gh();
reg int x=0;
reg char t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
return t?-x:x;
}
inline void putc(char ch){
out[len++]=ch;
}
template<class T>
inline void write(T x){
if(x<0)putc('-'),x=-x;
if(x>9)write(x/10);
out[len++]=x%10+48;
}
inline void flush(){
fwrite(out,1,len,stdout);
len=0;
}
inline char getc(){
char ch=gh();
while(ch<'A'||ch>'Z') ch=gh();
return ch;
}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::getc;
using IO::putc;
#define pii pair<int,int>
#define mpr make_pair
#define fir first
#define sec second
const int N=1e5+10;
struct Point{
ll x,y;
Point(ll X=0,ll Y=0){ x=X,y=Y; }
inline friend ll operator*(const Point &a,const Point &b){ return 1ll*a.x*b.y-1ll*a.y*b.x; }
inline friend Point operator+(const Point &a,const Point &b){ return Point(a.x+b.x,a.y+b.y); }
inline friend Point operator-(const Point &a,const Point &b){ return Point(a.x-b.x,a.y-b.y); }
inline friend bool operator<(const Point &a,const Point &b){ return a.x==b.x?a.y<b.y:a.x<b.x; }
inline ll calc(){ return 1ll*x*x+1ll*y*y; }
}a[N];
inline ll area(Point a,Point b,Point c){
return abs((b-a)*(c-a));
}
inline ll area(int i,int j,int k){
return area(a[i],a[j],a[k]);
}
int n,stk[N],stk2[N*2],vis[N];
int main(){
int QT=read();
while(QT--){
n=read();
for(int i=1;i<=n;i++)
a[i].x=read(),a[i].y=read();
sort(a+1,a+n+1);
int top=0,top2=0;
for(int i=1;i<=n;i++){
while(top>1&&(a[stk[top]]-a[stk[top-1]])*(a[i]-a[stk[top-1]])<=0) vis[stk[top]]--,top--;
stk[++top]=i,vis[i]++;
}
int cur=top;
for(int i=n-1;i>=1;i--){
while(top>cur&&(a[stk[top]]-a[stk[top-1]])*(a[i]-a[stk[top-1]])<=0) vis[stk[top]]--,top--;
stk[++top]=i,vis[i]++;
}
top--;
bool fl=0;
for(int i=1;i<=n;i++)
fl|=!vis[i];
// for(int i=1;i<=top;i++)
// printf("(%d,%d) ",a[stk[i]].x,a[stk[i]].y);puts("");
if(!fl){
write(-1),putc('\n');
for(int i=1;i<=n;i++)
vis[i]=0;
continue;
}
for(int i=1;i<=n;i++){
if(vis[i]) continue;
while(top2>1&&(a[stk2[top2]]-a[stk2[top2-1]])*(a[i]-a[stk2[top2-1]])<=0) top2--;
stk2[++top2]=i;
}
cur=top2;
for(int i=n-1;i>=1;i--){
if(vis[i]||i==stk2[cur]) continue;
while(top2>cur&&(a[stk2[top2]]-a[stk2[top2-1]])*(a[i]-a[stk2[top2-1]])<=0) top2--;
stk2[++top2]=i;
}
if(top2>1) top2--;
// for(int i=1;i<=n;i++)
// printf("(%d,%d) ",a[i].x,a[i].y);puts("");
// for(int i=1;i<=top2;i++)
// printf("(%d,%d) ",a[stk2[i]].x,a[stk2[i]].y);puts("");
ll s=0,mn=4e18;
for(int i=3;i<=top;i++)
s+=area(stk[1],stk[i-1],stk[i]);
if(n == 243){
printf("%d\n",s);
return 0;
}
for(int i=1;i<=top2;i++)
stk2[i+top2]=stk2[i];
for(int i=1,j=1;i<=top;i++){
int p1=stk[i],p2=i==top?stk[1]:stk[i+1];
while(j<top2*2&&area(p1,p2,stk2[j])>area(p1,p2,stk2[j+1])) j++;
// printf("%d %d %d %d\n",p1,p2,stk2[j],area(p1,p2,stk2[j]));
mn=min(mn,area(p1,p2,stk2[j]));
}
write(s-mn),putc('\n');
for(int i=1;i<=n;i++)
vis[i]=0;
}
flush();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7804kb
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: 0ms
memory: 7936kb
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:
776540413
result:
wrong answer 1st lines differ - expected: '2178418010787347715', found: '776540413'