求查哪里爆 long long 了
查看原帖
求查哪里爆 long long 了
555065
ChrysanthBlossom楼主2024/8/14 18:16

define 之后可过,但眼睛都瞪瞎了还瞪不出来。

#include<bits/stdc++.h>
#define ri register int
#define ll long long
#define mkp make_pair
//#define int long long
using namespace std;
const int maxn=1e5+7;
// 16:19-18:08
int n,k,x,y;
int xx[maxn],yy[maxn];
struct line{
	ll l,r;
	friend line operator & (line a,line b){
		return (line){max(a.l,b.l),min(a.r,b.r)};
	}
};
const ll inf=1e18;
void solve(){
	cin>>n>>k>>x>>y;
	for(ri i=1;i<=n;i++)cin>>xx[i]>>yy[i];
	if(x<0){
		for(ri i=1;i<=n;i++)xx[i]*=-1;
		x*=-1;
	}
	if(y<0){
		for(ri i=1;i<=n;i++)yy[i]*=-1;
		y*=-1;
	}
	ll sumx=0,sumy=0;
	for(ri i=1;i<=n;i++)sumx+=xx[i];
	for(ri i=1;i<=n;i++)sumy+=yy[i];
	ll presumx=0,presumy=0;
	ll ans=inf;
	if(abs(x)+abs(y)==0){
		cout<<0<<endl;
		return;
	}
	for(ri i=1;i<=n;i++){
		presumx+=xx[i];presumy+=yy[i];
		auto check=[&](int m){
			return abs(x-1ll*m*sumx-presumx)+abs(y-1ll*m*sumy-presumy)<=(1ll*m*n+i)*k;
		};
		line bf;
		// abs1>0,abs2>0
		bf=(line){0,inf};
		if(sumx>0)bf=bf&(line){0,(x-presumx)/sumx};
		else if(sumx<0)bf=bf&(line){(x-presumx)/sumx,inf};
		if(sumy>0)bf=bf&(line){0,(y-presumy)/sumy};
		else if(sumy<0)bf=bf&(line){(y-presumy)/sumy,inf};
		if(sumx+sumy+1ll*n*k>0)bf=bf&(line){(x+y-presumx-presumy-1ll*i*k)/(sumx+sumy+1ll*n*k),inf};
		else if(sumx+sumy+1ll*n*k<0)bf=bf&(line){0,-(x+y-presumx-presumy-1ll*i*k)/(sumx+sumy+1ll*n*k)};
		else if(x+y-presumx-presumy-1ll*i*k>0)bf=bf&(line){inf,0};
		if(bf.r>=bf.l){
			if(check(bf.l))ans=min(ans,1ll*bf.l*n+i);
			if(check(bf.l+1))ans=min(ans,1ll*(bf.l+1)*n+i);
		}
		// abs1<0,abs2>0
		bf=(line){0,inf};
		if(sumx>0)bf=bf&(line){(x-presumx)/sumx,inf};
		else if(sumx<0)bf=bf&(line){0,(x-presumx)/sumx};
		if(sumy>0)bf=bf&(line){0,(y-presumy)/sumy};
		else if(sumy<0)bf=bf&(line){(y-presumy)/sumy,inf};
		if(-sumx+sumy+1ll*n*k>0)bf=bf&(line){(-x+y+presumx-presumy-1ll*i*k)/(-sumx+sumy+1ll*n*k),inf};
		else if(-sumx+sumy+1ll*n*k<0)bf=bf&(line){0,-(-x+y+presumx-presumy-1ll*i*k)/(-sumx+sumy+1ll*n*k)};
		else if(-x+y+presumx-presumy-1ll*i*k>0)bf=bf&(line){inf,0};
		if(bf.r>=bf.l){
			if(check(bf.l))ans=min(ans,1ll*bf.l*n+i);
			if(check(bf.l+1))ans=min(ans,1ll*(bf.l+1)*n+i);
		}
		// abs1>0,abs2<0
		bf=(line){0,inf};
		if(sumx>0)bf=bf&(line){0,(x-presumx)/sumx};
		else if(sumx<0)bf=bf&(line){(x-presumx)/sumx,inf};
		if(sumy>0)bf=bf&(line){(y-presumy)/sumy,inf};
		else if(sumy<0)bf=bf&(line){0,(y-presumy)/sumy};
		if(sumx-sumy+1ll*n*k>0)bf=bf&(line){(x-y-presumx+presumy-1ll*i*k)/(sumx-sumy+1ll*n*k),inf};
		else if(sumx-sumy+1ll*n*k<0)bf=bf&(line){0,-(x-y-presumx+presumy-1ll*i*k)/(sumx-sumy+1ll*n*k)};
		else if(x-y-presumx+presumy-1ll*i*k>0)bf=bf&(line){inf,0};
		if(bf.r>=bf.l){
			if(check(bf.l))ans=min(ans,1ll*bf.l*n+i);
			if(check(bf.l+1))ans=min(ans,1ll*(bf.l+1)*n+i);
		}
		// abs1<0,abs2<0
		bf=(line){0,inf};
		if(sumx>0)bf=bf&(line){(x-presumx)/sumx,inf};
		else if(sumx<0)bf=bf&(line){0,(x-presumx)/sumx};
		if(sumy>0)bf=bf&(line){(y-presumy)/sumy,inf};
		else if(sumy<0)bf=bf&(line){0,(y-presumy)/sumy};
		if(-sumx-sumy+1ll*n*k>0)bf=bf&(line){(-x-y+presumx+presumy-1ll*i*k)/(-sumx-sumy+1ll*n*k),inf};
		else if(-sumx-sumy+1ll*n*k<0)bf=bf&(line){0,-(-x-y+presumx+presumy-1ll*i*k)/(-sumx-sumy+1ll*n*k)};
		else if(-x-y+presumx+presumy-1ll*i*k>0)bf=bf&(line){inf,0};
		if(bf.r>=bf.l){
			if(check(bf.l))ans=min(ans,1ll*bf.l*n+i);
			if(check(bf.l+1))ans=min(ans,1ll*(bf.l+1)*n+i);
		}
	}
	if(ans!=inf)cout<<ans<<endl;
	else cout<<-1<<endl;
}
signed main(){
	ios::sync_with_stdio(0);
	int T;cin>>T;
	while(T--)solve();
	return 0;
}
2024/8/14 18:16
加载中...