RYIP在线题库
首 页   >   习题练习   >   提交
Problem1893--坐标

1893: 坐标

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

【 Description 】

给定平面上的一个坐标 (a, b)。接下来,我们对这个坐标按顺序执行N次操作。第i次操作(1 i N)是将坐标的x值增加xiy值增加yi。因此N次操作结束后,坐标将变为 (c, d),其中 c = a + x1 + x2 + x3 + … + xNd = b + y1 + y2 + y3 + … + yN。 假设现在已经知道了一开始的坐标 (a, b) 最终的坐标 (c, d),而N次操作中恰好混入了一次多余的操作。你能判断哪一次操作是多余的吗?

【 Input 】

第一行为四个整数a, b, c, d,分别表示最开始的坐标、操作结束时的坐标。 
第二行为一个整数N,表示操作次数(多余的那次操作未计入在内)。 
接下来N + 1行,每行两个整数xi, yi,按顺序表示每一次的操作。保证其中恰好有一次操作是多余的。

【 Output 】

一个整数k,表示输入的第k次操作是多余的。
也就是说,将N + 1次操作中的第k次操作删去,按顺序执行其他的N次操作,坐标 (a, b) 正好可以变为 (c, d)
如果有多个满足要求的答案,请输出编号最小的。

【 Sample Input 】

1 2 4 5
1
3 3
1 2

【 Sample Output 】

2

【HINT】

对于30%的测试点,保证1 ≤ N ≤ 2。
对于60%的测试点,保证1 ≤ N ≤ 2000。
对于100%的测试点,保证1 ≤ N ≤ 2000000,-10000 ≤ a, b, xi, yi ≤ 10000。