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) - (2_x_, 0) - (3_x_, x) - (4_x_, 0) - … - (2_kx_, 0) - (2_kx_ + 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
3 1
output
1.000000000000
input
1 3
output
-1
input
4 1
output
1.250000000000
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了好多次。。。。
1/*************************************************************************
2> File Name: code/cf/#320/C.cpp
3> Author: 111qqz
4> Email: rkz2013@126.com
5> Created Time: 2015年11月10日 星期二 16时54分46秒
6************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#include<cctype>
21#define fst first
22#define sec second
23#define lson l,m,rt<<1
24#define rson m+1,r,rt<<1|1
25#define ms(a,x) memset(a,x,sizeof(a))
26using namespace std;
27const double eps = 1E-10;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30typedef long long LL;
31const int inf = 0x3f3f3f3f;
32const LL linf =1LL<<60;
33LL a,b;
34int dblcmp(double d)
35{
36return d<-eps?-1:d>eps;
37}
38LL bin(LL l,LL r)
39{
40LL res = -1;
41while (l<=r)
42{
43LL mid = (l+r)>>1;
44double x=(a+b)*1.0/(2*mid);
45if (dblcmp(x-b)>=0)
46{
47l = mid+1;
48res = mid;
49}
50else
51r = mid -1;
52}
53return res;
54}
55int main()
56{
57#ifndef ONLINE_JUDGE
58// freopen("in.txt","r",stdin);
59#endif
60
61cin>>a>>b;
62LL k = bin(1LL,linf);
63if (a<b)
64{
65puts("-1");
66}
67else
68{
69// LL k = bin(1LL,linf);
70printf("%.12fn",(a+b)*1.0/(2.0*k));
71}
72
73
74#ifndef ONLINE_JUDGE
75#endif
76fclose(stdin);
77return 0;
78}