Submission #2967528

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
int n;
D t[100005],x[100005];
int main(void){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t[i]>>x[i];
    }
    for(int i=n;i>0;i--){
        t[i]-=t[i-1];
    }
    D l=0,r=1000001;
    while(r-l>0.000001){
        D m=(l+r)/2;
        D a[100005],b[100005];
        a[0]=0;
        b[0]=0;
        bool o=true;
        for(int i=0;i<n&&o;i++){
            D v=t[i+1]*m;
            if(x[i]-v<=x[i+1]&&x[i+1]<=x[i]+v){
                a[i+1]=a[i]-v;
                b[i+1]=b[i]+v;
                if(a[i]-v<=x[i+1]&&x[i+1]<=b[i]+v){
                    a[i+1]=min(a[i+1],x[i]-v);
                    b[i+1]=max(b[i+1],x[i]+v);
                }
            }else if(a[i]-v<=x[i+1]&&x[i+1]<=b[i]+v){
                a[i+1]=x[i]-v;
                b[i+1]=x[i]+v;
            }else{
                o=false;
            }
        }
        if(o)r=m;
        else l=m;
    }
    printf("%.6lf\n",l);
}

Submission Info

Judge Result