QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#744425#9520. Concave HullzzuqyWA 1ms7948kbC++202.9kb2024-11-13 21:53:152024-11-13 21:53:17

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 21:53:17]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7948kb
  • [2024-11-13 21:53:15]
  • 提交

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'