题面
题目描述
给定 \(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\)。
样例输入
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
0
399999999
样例解释
该组样例共有四组测试数据。
- 对于第一组测试数据，取 \(m=1\)，\((x_0',y_0')=(1,1)\) 满足条件，可以证明不存在更小的 \(m\) 满足条件；
- 对于第二组测试数据，可以证明不存在任何非负整数 \(m\) 满足条件；
- 对于第三组测试数据，取 \(m=0\) 满足条件，可以证明不存在更小的 \(m\) 满足条件。
数据规模与约定
设 \(\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\)。
【提示】
本题输入文件较大，请使用较为快速的输入方式。
题解
方法概述
简单的分讨和朴素（指无需复杂算法）的解决。
相信分讨以解决本题。有时候不一定非要找到一个可以解决所有情况的通解……这很可能导致在简单题上花费多余的时间精力（而且最终不一定做得出来）（←本人）
写部分分也是同理，它们有时候起到引导正解的作用。当然，如果能直接想到正解……%%%
正解做法
其实看到数据范围就想用二分（？）感觉像是\(O(n\log n)\)来做。结果最后没用二分，貌似大家都是分讨nya？（以及推式子的dalao）
