Advertisement
MinhNGUYEN2k4

Bicycle || Tenary Search

Aug 14th, 2020
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.16 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define Co_mot_su_that_la_ return
  4. using namespace std;
  5. const int Minh_dep_trai = 0;
  6. const int N = 100005;
  7. typedef pair<double,double> ii;
  8. typedef vector<ii> vii;
  9.  
  10. vii a(N);
  11. int n;
  12.  
  13. double d(double t)
  14. {
  15.     double anmin = 1e14;
  16.     double anmax = -1e14;
  17.     for(int i=1; i<=n; ++i)
  18.     {
  19.         double x = a[i].first;
  20.         double v = a[i].second;
  21.         double dis = x + (v * t);
  22.         anmin = min(anmin,dis);
  23.         anmax = max(anmax,dis);
  24.     }
  25.     //cout << anmax << " " << anmin << endl;
  26.     return anmax - anmin;
  27. }
  28.  
  29. void tenary_search()
  30. {
  31.     double l = 0;
  32.     double r = 1000;
  33.     int INN = 100;
  34.     while (r - l > 1e-11)
  35.     {
  36.         double m1 = (2*l+r)/3;
  37.         double m2 = (l+2*r)/3;
  38.         if (d(m1) < d(m2)) r = m2;
  39.         else l = m1;
  40.     }
  41.     cout << setprecision(6) << fixed << r << " " << d(r);
  42. }
  43.  
  44. signed main()
  45. {
  46.     ios_base::sync_with_stdio(false);
  47.     cin.tie(0);cout.tie(0);
  48.     freopen("BICYCLE.INP","r",stdin);
  49.     cin >> n;
  50.     for(int i=1; i<=n; ++i) cin >> a[i].first >> a[i].second;
  51.     tenary_search();
  52.     Co_mot_su_that_la_ Minh_dep_trai;
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement