UOJ Logo Universal Online Judge

UOJ

#865. 【统一省选2024】季风

附件下载 统计

生活在二维平面的小 X 准备拜访小 Y,但由于气候的变化,平面上刮起了季风。小 X 想知道季风的影响下,TA 至少要多少天能够到达小 Y 的家,但小 X 也是第一次遇见这种怪事,所以请精通算法的你来帮忙。

题目描述

给定 n,k,x,y2n 个整数 x0,y0,x1,y1,,xn1,yn1

找到最小的非负整数 m,使得存在 2m 个实数 x0,y0,x1,y1,,xm1,ym1 满足以下条件,或报告不存在这样的 m

  • i=0m1(xi+ximodn)=x
  • i=0m1(yi+yimodn)=y
  • 0im1,|xi|+|yi|k

特别地,m=0 时,认为 i=0m1(xi+ximodn)i=0m1(yi+yimodn) 均为 0

输入格式

本题有多组测试数据。输入的第一行一个整数 T 表示测试数据组数。

对于每组测试数据,

  • 第一行四个整数 n,k,x,y
  • 接下来 n 行,第 i 行两个整数 xi1,yi1

输出格式

对于每组测试数据输出一行一个整数,如果存在满足题意的 m,输出其最小可能值,否则输出 1

样例 1

input

4
1 2 2 2
1 1
1 2 -2 -2
1 1
1 2 0 0
1 1
2 100000000 100000000 100000000
-99999999 0
-100000000 0

output

1
-1
0
399999999

explanation

该组样例共有四组测试数据。 - 对于第一组测试数据,取 m=1(x0,y0)=(1,1) 满足条件,可以证明不存在更小的 m 满足条件; - 对于第二组测试数据,可以证明不存在任何非负整数 m 满足条件; - 对于第三组测试数据,取 m=0 满足条件,可以证明不存在更小的 m 满足条件。

【样例 2】

见附件中的 wind2.in/ans

该组样例共有八十组测试数据,所有测试数据均满足 n=1,其中测试数据 120 满足特殊性质 A,2140 满足特殊性质 B,4160 满足特殊性质 C。

【样例 3】

见附件中的 wind3.in/ans

该组样例共有六十组测试数据,所有测试数据均满足 n=200,其中测试数据 120 满足特殊性质 A,2140 满足特殊性质 B。

子任务

n 为单个测试点内所有测试数据 n 的和。对于所有测试数据:

  • 1T5×104
  • 1n1051n106
  • 0|x|,|y|,|xi|,|yi|,k108
测试点编号 n n 特殊性质
1 1 300 A
2 1 300 B
3 1 300 C
4 1 300
5 200 5000 A
6 200 5000 B
7 200 5000
8 104 105 A
9 104 105 B
10 105 106
  • 特殊性质 A:0in1|xi|+|yi|k
  • 特殊性质 B:k=0
  • 特殊性质 C:x0=y0=0

【提示】

本题输入文件较大,请使用较为快速的输入方式。

时间限制:0.5s

空间限制:512MB