QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#721022 | #9520. Concave Hull | ffffyc | WA | 10ms | 7856kb | C++14 | 3.6kb | 2024-11-07 15:00:02 | 2024-11-07 15:00:05 |
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{
int x,y;
Point(int X=0,int 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--;
// for(int i=1;i<=top;i++)
// printf("(%d,%d) ",a[stk[i]].x,a[stk[i]].y);puts("");
if(top==n){
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;
}
top2--;
// 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]);
// printf("%d\n",s);
for(int i=1;i<=top2;i++)
stk2[i+top2]=stk2[i];
if(top2<=10){
for(int i=1;i<=top;i++){
int p1=stk[i],p2=i==top?stk[1]:stk[i+1];
for(int j=1;j<=top2;j++)
mn=min(mn,area(p1,p2,stk2[j]));
}
}else{
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: 5680kb
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: 5624kb
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: 10ms
memory: 7856kb
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 1164835025329039520 1527446155241140517 1807368432185303666 1236918659444944569 1306839249967484778 1984123720246784099 1868728080720036006 667458140583450322 2127932992585026491 -...
result:
wrong answer 16th lines differ - expected: '447172929227332597', found: '-3519592589969095487'