fork download
copy 
  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. #define N 100010
  6. int n, v[N], s[N];
  7. double x(int i, double t){
  8.     return s[i]+v[i]*t;
  9. }
  10. double f(double t){
  11.     double minx, maxx;
  12.     minx = maxx = x(1, t);
  13.     for(int i=2; i<=n; i++){
  14.         double xi = x(i, t);
  15.         minx = min(minx, xi);
  16.         maxx = max(maxx, xi);
  17.     }
  18.     return (maxx-minx);
  19. }
  20.  
  21. int main(){
  22.     scanf("%d", &n);
  23.     for(int i=1; i<=n; i++){
  24.         scanf("%d%d", v+i, s+i);
  25.     }
  26.     int mins=s[1], maxs=s[1];
  27.     for(int i=2; i<=n; i++){
  28.         mins = min(mins, s[i]);
  29.         maxs = max(maxs, s[i]);
  30.     }
  31.     double l=0, r=maxs-mins;
  32.     while(r-l > 1e-10){
  33.         double m1=(2*l+r)/3, m2=(l+2*r)/3;
  34.         if(f(m1) < f(m2)){
  35.             r = m2;
  36.         }else{
  37.             l = m1;
  38.         }
  39.     }
  40.     printf("%.2f\n", f(l));
  41.     return 0;
  42. }
  43.  
Success #stdin #stdout 0s 4532KB
comments (?)
stdin
copy 
3
1 1
2 0
3 0
stdout
copy 
0.50
https://ideone.com/i93bih
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

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!