codeforces #320 div 2 C. A Problem about Polyline(计算几何?数学)

C. A Problem about Polyline
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

There is a polyline going through points (0, 0) – (x, x) – (2x, 0) – (3x, x) – (4x, 0) – … - (2kx, 0) – (2kx + x, x) – ….

We know that the polyline passes through the point (a, b). Find minimum positive value x such that it is true or determine that there is no such x.

Input

Only one line containing two positive integers a and b (1 ≤ a, b ≤ 109).

Output

Output the only line containing the answer. Your answer will be considered correct if its relative or absolute error doesn’t exceed10 - 9. If there is no such x then output  - 1 as the answer.

Sample test(s)
input

output

input

output

input

output

Note

You can see following graphs for sample 1 and sample 3.

                                  

 

题意:
  有从原点开始,斜率分别为1和-1的折线周期下去,问是否存在x使得整点(a,b)在折线上,存在的话求最小的x,无解输出-1.
 
思路:由于斜率为1,所以x>=y.那么x
对于x>=y的情况:我们发现(a,b)点如果是落在斜率为1的折线上,那么该折线与x轴的交点为(a-b,0)
如果(a,b)点落在落在斜率为-1的折线上,那么该折线与x轴的交点为(a+b,0) 
分析可知,如果a+b为奇数,那么一定会落在斜率为-1的折线上,如果a-b为偶数,一定会落在斜率为1的折线上。
而(a+b)不为偶数和(a-b)补为偶数不可能同时成立。
因为碎玉x>=y的情况一定有解。
二分答案即可(其实还有一种比较偷懒(比较聪明?)的办法是…不去考虑是否一定有解。把二分的初始条件设置为-1就好)
不过证明无解也并不难想。
 
需要注意的是精度问题。。。eps要记得根据题目调整。。。比如这道题要求1E-9…
eps至少比要求的多两位才保险。。。。
因为忘记调整eps(因为一般题目要求都是1E-6。。。所以我eps写的是1E-8)而wa了好多次。。。。
 

View Code

 

 
 
Posted in ACM

说点什么

您将是第一位评论人!

提醒
wpDiscuz