← 返回题目

题库练习「联合省选 2024」季风

← 上一题下一题 →

A6647 | $「联合省选 2024」季风$

来源省选

时间限制500ms

内存限制512MB

通过 / 提交0/0

题目描述

给定 $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$。

输入格式

从文件 wind.in 中读入数据。 **本题有多组测试数据**。输入的第一行一个整数 $T$ 表示测试数据组数。 对于每组测试数据， - 第一行四个整数 $n,k,x,y$； - 接下来 $n$ 行，第 $i$ 行两个整数 $x_{i-1},y_{i-1}$。

输出格式

输出到文件 wind.out 中。 对于每组测试数据输出一行一个整数，如果存在满足题意的 $m$，输出其最小可能值，否则输出 $-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

C++ 编辑器

输入

输出