题目分析
首先，明显 $0\sim n-1,0\sim m-1$ 不好，因此我们统一使用以 $1$ 开始的下标。
其次，对于“$\large x_{i\bmod n}$”，那么我们为了便于分析（但事实上在后文就会发现只会用到 $x_1\sim x_n$），直接让其无限循环，即：令 $\large \forall x_i=x_{i\bmod n}$。对 $\large y_{i \bmod n}$ 进行同样的处理。
同样地，为了便于分析，以下暂不考虑 $m=0$ 的情况会出现，因为 $m=0$ 最小成立显然当且仅当 $x=y=0$，特判即可。
考虑到：\(\large \sum\limits_{i=1}^m(x'_i+x_i)=x\)，那么：\(\large \sum\limits_{i=1}^mx'_i=x-\sum\limits_{i=1}^mx_i\)。
同理，有：\(\large \sum\limits_{i=1}^my'_i=y-\sum\limits_{i=1}^my_i\)。
因为 \(\vert x'_i\vert+\vert y'_i\vert \leq k\)，则 \(\large\Bigg\vert \sum\limits_{i=1}^mx'_i\Bigg\vert +\Bigg\vert\sum\limits_{i=1}^my'_i\Bigg\vert \leq mk\)。
结合两式，有：\(\large\Bigg\vert x-\sum\limits_{i=1}^mx_i\Bigg\vert +\Bigg\vert y-\sum\limits_{i=1}^my_i\Bigg\vert \leq mk\)。
一个很明显的结论就是 $p \leq \vert p \vert$ 恒成立，那么 $m$ 需要同时满足以下条件：
\[\left\{ \begin{array}{} \large x-\sum\limits_{i=1}^mx_i+y-\sum\limits_{i=1}^my_i\leq mk\\ \large x-\sum\limits_{i=1}^mx_i+\sum\limits_{i=1}^my_i-y\leq mk\\ \large \sum\limits_{i=1}^mx_i-x+y-\sum\limits_{i=1}^my_i\leq mk\\ \large \sum\limits_{i=1}^mx_i-x+\sum\limits_{i=1}^my_i-y\leq mk\\ \end{array} \right.\]等价于需要满足：
\[\left\{ \begin{aligned} &\large \sum_{i=1}^m(x_i+y_i-k)\geq x+y\\ &\large \sum_{i=1}^m(x_i-y_i-k)\geq x-y\\ &\large \sum_{i=1}^m(-x_i+y_i-k)\geq -x+y\\ &\large \sum_{i=1}^m(-x_i-y_i-k)\geq -x-y\\ \end{aligned} \right.\]因此，只有当 $m$ 满足上述条件时，$m$ 才成立。
现在，针对第一种展开分析。（剩下三种分析见后文）
设 $\large f_i=\sum\limits_{j=1}^i(x_j+y_j-k)$，则有 $\large f_m\geq x+y$。
设 $m=qn+i$，其中 $i=m\bmod n$（或 $i=n$）。
考虑到 $x_j,y_j$ 均以 $n$ 为周期循环，有 $\large f_m=f_{qn}+f_i=q\times f_n+f_i$。
则：$\large q\times f_n+f_i\geq x+y$。
不等式，明显分类讨论。
-
$\large f_n>0$ 时，解得 $\large q_i\geq \Bigg\lceil\dfrac{x+y-f_i}{f_n}\Bigg\rceil$。
- $\large f_n<0$ 时，解得 $\large q_i\leq \Bigg\lfloor\dfrac{x+y-f_i}{f_n}\Bigg\rfloor$。
- $f_n=0$ 时，需要继续分类。
- 若 $\large f_i<x+y$，则此时无解，与条件相悖。
- 否则，有解，解为 $q_i=0$。
我们使用 $\large [l_i,r_i]$ 来描述 $\large q_i$ 的上下界，每次更新 $l_i,r_i$ 即可，最终答案即为 $\large \min\limits_{i=1}^{n}(l_i\times n+1)$。
但需要注意的是，$i\in[1,n]$，而不是 $[1,n)$。因为我们需要考虑 $m\bmod n=0$ 的情况，那么不妨令 $q_n=\dfrac{m}{n}-1,i=n$，便于处理。
那么至此，我们就求出了满足第一个不等式 $\large \sum\limits_{i=1}^m(x_i+y_i-k)\geq x+y$ 的 所有区间 $[l_i，r_i]$。
同理再进行三次操作，求出最终所有公共的 $[l_i,r_i]$ ，答案即 $\large \min\limits_{i=1}^{n}(l_i\times n+1)$。
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
const ll MAX=(1ll<<60);
const int N=1e5;
int n,k,x,y,X[N+1],Y[N+1];
ll l[N+1],r[N+1];
inline void solve(int opx,int opy){
static ll f[N+1];
ll t=opx*x+opy*y;
for(int i=1;i<=n;i++)f[i]=f[i-1]+opx*X[i]+opy*Y[i]+k;
if(f[n]==0){
for(int i=1;i<=n;i++){
if(f[i]<t)r[i]=-MAX;
}
}else if(f[n]>0){
for(int i=1;i<=n;i++){
if(t>f[i])l[i]=max(l[i],(t-f[i])/f[n] + ( (t-f[i])%f[n]>0 ) );
}
}else{
for(int i=1;i<=n;i++){
if(f[i]<t)r[i]=-MAX;
else r[i]=min(r[i],(t-f[i])/f[n]);
}
}
}
inline void work(){
scanf("%d %d %d %d",&n,&k,&x,&y);
for(int i=1;i<=n;i++){
scanf("%d %d",X+i,Y+i);
l[i]=0;r[i]=MAX;
}
if(x==0&&y==0){
printf("0\n");
return;
}solve(1,1);solve(1,-1);solve(-1,1);solve(-1,-1);
ll ans=MAX;
for(int i=1;i<=n;i++){
if(l[i]<=r[i])ans=min(ans,l[i]*n+i);
}printf("%lld\n",(ans<MAX?ans:-1));
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
int T;
scanf("%d",&T);
while(T--)work();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
