codeforces #320 div 2 C. A Problem about Polyline(计算几何？数学)-白红宇

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

阅读量：4620 次

发布时间：2019-06-09

本文共 2739 字，大约阅读时间需要 9 分钟。

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

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.

$\text{[math]}$

题意：

　　有从原点开始，斜率分别为1和-1的折线周期下去，问是否存在x使得整点（a,b)在折线上，存在的话求最小的x，无解输出-1.

思路：由于斜率为1，所以x>=y.那么x<y的情况一定无解。

对于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
       
         9 #include
        
         10 #include
         
          11 #include
          
           12 #include
           
            13 #include
            
             14 #include
             
              15 #include
              16 #include
               
                17 #include
                
                 18 #include
                 
                  19 #include
                  
                   20 #include
                   
                    21 #define fst first 22 #define sec second 23 #define lson l,m,rt<<124 #define rson m+1,r,rt<<1|125 #define ms(a,x) memset(a,x,sizeof(a))26 using namespace std;27 const double eps = 1E-10;28 const int dx4[4]={ 1,0,0,-1};29 const int dy4[4]={ 0,-1,1,0};30 typedef long long LL;31 const int inf = 0x3f3f3f3f;32 const LL linf =1LL<<60;33 LL a,b;34 int dblcmp(double d)35 {36 return d<-eps?-1:d>eps;37 }38 LL bin(LL l,LL r)39 {40 LL res = -1;41 while (l<=r)42 {43 LL mid = (l+r)>>1;44 double x=(a+b)*1.0/(2*mid);45 if (dblcmp(x-b)>=0) 46 {47 l = mid+1;48 res = mid;49 }50 else51 r = mid -1;52 }53 return res;54 }55 int main()56 {57 #ifndef ONLINE_JUDGE 58 // freopen("in.txt","r",stdin);59 #endif60 61 cin>>a>>b;62 LL k = bin(1LL,linf);63 if (a

View Code

转载于:https://www.cnblogs.com/111qqz/p/4956236.html

你可能感兴趣的文章