QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#744425 | #9520. Concave Hull | zzuqy | WA | 1ms | 7948kb | C++20 | 2.9kb | 2024-11-13 21:53:15 | 2024-11-13 21:53:17 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define db double
#define INF 1100000000
#define inf 100000000000000000ll
#define ldb long double
#define pb push_back
#define put_(x) printf("%d ",x)
#define putl_(x) printf("%lld ",x)
#define get(x) x=read()
#define putl(x) printf("%lld\n",x)
#define rep(p,n,i) for(int i=p;i<=n;i+=1)
#define fep(n,p,i) for(int i=n;i>=p;--i)
#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define pii pair<int,int>
#define mk make_pair
#define gf(x) scanf("%lf",&x)
#define pf(x) ((x)*(x))
#define ui unsigned
#define sq sqrt
#define l(w) t[w].l
#define r(w) t[w].r
#define x(w) t[w].x
#define tag(w) t[w].tag
#define sum(w) t[w].sum
#define sc(A) scanf("%d",&A)
#define scl(A) scanf("%lld",&A)
#define scs(A) scanf("%s",A);
#define put(A) printf("%d\n",A)
#define min(x,y) (x>=y?y:x)
#define max(x,y) (x>=y?x:y)
#define sub(x,y) (x-y<0?x-y+mod:x-y)
#define uint unsigned int
#define mod 1000000007
#define zz p<<1
using namespace std;
int T;
int n,top;
const int MAXN=100010;
struct wy
{
ll x,y;
wy operator +(wy a){return wy(x+a.x,y+a.y);}
wy operator -(wy a){return wy{x-a.x,y-a.y};}
wy operator -(){return wy(-x,-y);}
ll operator *(wy a){return x*a.x+y*a.y;}
int friend operator %(wy a,wy b){return a.x*b.y-a.y*b.x;}
ll operator <(wy a){return y==a.y?x<a.x:y<a.y;}
ll operator ~(){return x*x+y*y;}
}a[MAXN],LTL,g[MAXN],v[MAXN];
int para(wy a,wy b){return a%b==0;}
int Toleft(wy a,wy b){return a%b>0;}
int cmpltl(wy a,wy b){return para(a=a-LTL,b=b-LTL)?~a<~b:a%b>0;}
int s[MAXN];
void Put(wy a){cout<<a.x<<' '<<a.y<<endl;}
int main()
{
sc(T);
while(T--)
{
sc(n);
rep(1,n,i)
{
int x,y;
sc(x);sc(y);
a[i]=wy(x,y);
}
LTL=*min_element(a+1,a+1+n);
//Put(LTL);
sort(a+1,a+1+n,cmpltl);
//rep(1,n,i)Put(a[i]);
//cout<<endl;
//Put(a[2]-LTL);
//Put(a[3]-LTL);
//cout<<(a[2]-LTL)%(a[3]-LTL)<<endl;
//cout<<Toleft(a[2]-LTL,a[3]-LTL)<<endl;
//cout<<cmpltl(a[2],a[3])<<endl;
top=0;
rep(1,n,i)
{
while(top>1&&Toleft(a[i]-a[s[top-1]],a[s[top]]-a[s[top-1]]))--top;
s[++top]=i;
}
if(top<=2||top==n)
{
puts("-1");
continue;
}
//rep(1,top,i)Put(a[s[i]]);
//put(top);
int cnt=0,ww=1;
rep(1,n,i)
{
if(s[ww]==i)
{
++ww;
continue;
}
g[++cnt]=a[i];
}
//put(cnt);
LTL=*min_element(g+1,g+1+cnt);
sort(g+1,g+1+cnt,cmpltl);
int top1=0;
rep(1,cnt,i)
{
while(top1>1&&Toleft(g[i]-v[top1-1],v[top1]-v[top1-1]))--top1;
v[++top1]=g[i];
}
ll ans=0;
rep(2,top-1,i)
{
ans+=(a[s[i]]-a[s[1]])%(a[s[i+1]]-a[s[1]]);
}
//putl(ans);
s[++top]=s[1];v[++top1]=v[1];
ll cc=ans;
ww=1;
rep(1,top-1,i)
{
while(1)
{
cc=min(cc,(a[s[i]]-a[s[i-1]])%(v[ww]-a[s[i-1]]));
if(ww==top1)break;
if((a[s[i]]-a[s[i-1]])%(v[ww]-v[ww-1])>0)break;
++ww;
}
}
putl(cc==0?-1:ans-cc);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7948kb
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: 5884kb
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:
64232673507 20642394258 17294914912 6317155476 32557749464 -1 11033714271 28017694179 3759187323 7757802775
result:
wrong answer 1st lines differ - expected: '2178418010787347715', found: '64232673507'