fork(2) download
copy 
  1. /* Ternary Search */
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <cmath>
  5. #define esp 1e-16
  6. #define maxn 100100
  7. using namespace std;
  8. long double l,r,m1,m2;
  9. int a[maxn];
  10. int v[maxn];
  11. int n;
  12.  
  13. long double get(long double time)
  14. {
  15.     long double ll = a[1]+v[1]*time;
  16.     long double rr = a[1]+v[1]*time;
  17.     for (int i=2; i<=n; i++)
  18.     {
  19.         ll = min(ll,a[i]+v[i]*time);
  20.         rr = max(rr,a[i]+v[i]*time);
  21.     }
  22.     return ((rr-ll)/2);
  23. }
  24.  
  25. int main()
  26. {
  27.     ios::sync_with_stdio(false);
  28.     cin>>n;
  29.     for (int i=1; i<=n; i++) cin>>a[i];
  30.     for (int i=1; i<=n; i++) cin>>v[i];
  31.     l = 0;
  32.     r = 1e9 + 1;
  33.  
  34.     while (l<=r-esp)
  35.     {
  36.         m1 = l + (r-l)/3;
  37.         m2 = r - (r-l)/3;
  38.         long double res1 = get(m1);
  39.         long double res2 = get(m2);
  40.         if (res1<=res2) r = m2;
  41.         else
  42.             l = m1;
  43.     }
  44.     long double res = get(l);
  45.     int nm;
  46.     if (res==0) nm = 0;
  47.     else
  48.         nm = log10(res)+1;
  49.     nm+=3;
  50.     cout.precision(nm);
  51.     cout<<res;
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0s 4188KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DXZE7B
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!