【统一省选2024】季风 - 题目 - Universal Online Judge

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

题目描述

给定 $n,k,x,y$ 和 $2n$ 个整数 $x_0,y_0,x_1,y_1,\dots,x_{n-1},y_{n-1}$。

找到最小的非负整数 $m$，使得存在 $2m$ 个实数 $x_0',y_0',x_1',y_1',\dots,x_{m-1}',y_{m-1}'$ 满足以下条件，或报告不存在这样的 $m$：

$\sum \limits_{i=0}^{m-1} (x_i'+x_{i \bmod n})=x$；
$\sum \limits_{i=0}^{m-1} (y_i'+y_{i \bmod n})=y$；
$\forall 0\leq i\leq m-1,|x_i'|+|y_i'|\leq k$。

特别地，$m=0$ 时，认为 $\sum \limits_{i=0}^{m-1} (x_i'+x_{i \bmod n})$ 和 $\sum \limits_{i=0}^{m-1} (y_i'+y_{i \bmod n})$ 均为 $0$。

输入格式

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

对于每组测试数据，

第一行四个整数 $n,k,x,y$；
接下来 $n$ 行，第 $i$ 行两个整数 $x_{i-1},y_{i-1}$。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

提示

【样例 1 解释】

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

【样例 2】

见附件中的 wind2.in/ans。

该组样例共有八十组测试数据，所有测试数据均满足 $n=1$，其中测试数据 $1\sim 20$ 满足特殊性质 A，$21\sim 40$ 满足特殊性质 B，$41\sim 60$ 满足特殊性质 C。

【样例 3】

见附件中的 wind3.in/ans。

该组样例共有六十组测试数据，所有测试数据均满足 $n=200$，其中测试数据 $1\sim 20$ 满足特殊性质 A，$21\sim 40$ 满足特殊性质 B。

【子任务】

设 $\sum n$ 为单个测试点内所有测试数据 $n$ 的和。对于所有测试数据：

$1\leq T\leq 5\times 10^4$；
$1\leq n\leq 10^5$，$1\leq \sum n \leq 10^6$；
$0\leq |x|,|y|,|x_i|,|y_i|,k\leq 10^8$。

测试点编号	$n\leq$	$\sum n\leq$	特殊性质
$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$	$10^4$	$10^5$	A
$9$	$10^4$	$10^5$	B
$10$	$10^5$	$10^6$	无

特殊性质 A：$\forall 0\leq i \leq n-1$，$|x_i|+|y_i| \leq k$；
特殊性质 B：$k=0$；
特殊性质 C：$x_0=y_0=0$。

【提示】

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

时间限制：$\texttt{0.5s}$

空间限制：$\texttt{512MB}$

Universal Online Judge

UOJ

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