race time - convex hull trick

#include <bits/stdc++.h>
using namespace std;
double eps = 1e-7;
typedef pair<int,int> pii;
struct timeline
{
    int slope, intercept;
    double stime, ftime;
    timeline(int s, int i, double st, double ft)
    {
        slope = s;
        intercept = i;
        stime = st;
        ftime = ft;
    }
};
bool is_over(pii x, timeline y)
{
    double x1 = (x.first*y.stime)+x.second;
    double x2 = (x.first*y.ftime)+x.second;

    double y1 = (y.slope*y.stime)+y.intercept;
    double y2 = (y.slope*y.ftime)+y.intercept;

    if(x1 >= y1-eps && x2 >= y2-eps)
        return true;
    return false;
}
bool is_under(pii x, timeline y)
{
    double x1 = (x.first*y.stime)+x.second;
    double x2 = (x.first*y.ftime)+x.second;

    double y1 = (y.slope*y.stime)+y.intercept;
    double y2 = (y.slope*y.ftime)+y.intercept;

    if(x1 <= y1+eps && x2 <= y2+eps)
        return true;
    return false;
}
double find_intersection(pii x, timeline y)
{
    // cout<<x.first<<" "<<x.second<<" "<<y.slope<<" "<<y.intercept<<"\n";
    if(x.first == y.slope)
        return -100;
    return ((y.intercept - x.second)*1.0)/((x.first - y.slope)*1.0);
}
vector <pii> A;
int main()
{
    // freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0);
    int n, k;
    scanf("%d %d", &n, &k);
    A.resize(n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d %d", &A[i].first, &A[i].second);
    }
    sort(A.rbegin(), A.rend());
    vector <timeline> max_stack;
    for (int i = 0; i < n; ++i)
    {
        double st = 0.0, ft = 0.0;
        while(!max_stack.empty() && is_over(A[i], max_stack.back()))
        {
            ft = max_stack.back().ftime;
            max_stack.pop_back();
        }
        if(max_stack.empty())
        {
            ft = k;
            max_stack.push_back(timeline(A[i].first, A[i].second, st, ft));
        }
        else
        {
            ft = find_intersection(A[i], max_stack.back());
            if(ft >= st+eps)
            {
                timeline temp = max_stack.back();
                max_stack.pop_back();
                temp.stime = ft;
                max_stack.push_back(temp);
                max_stack.push_back(timeline(A[i].first, A[i].second, st, ft));
            }
        }
    }
    sort(A.begin(), A.end());
    vector <timeline> min_stack;
    for (int i = 0; i < n; ++i)
    {
        double st = 0.0, ft = 0.0;
        while(!min_stack.empty() && is_under(A[i], min_stack.back()))
        {
            ft = min_stack.back().ftime;
            min_stack.pop_back();
        }
        if(min_stack.empty())
        {
            ft = k;
            min_stack.push_back(timeline(A[i].first, A[i].second, st, ft));
        }
        else
        {
            ft = find_intersection(A[i], min_stack.back());
            if(ft >= st+eps)
            {
                timeline temp = min_stack.back();
                min_stack.pop_back();
                temp.stime = ft;
                min_stack.push_back(temp);
                min_stack.push_back(timeline(A[i].first, A[i].second, st, ft));
            }
        }
    }
    reverse(max_stack.begin(), max_stack.end());
    reverse(min_stack.begin(), min_stack.end());

    // for (int i = 0; i < max_stack.size(); ++i)
    // {
    //  cout<<max_stack[i].slope<<" "<<max_stack[i].intercept<<" "<<max_stack[i].stime<<" "<<max_stack[i].ftime<<"\n";
    // }
    // cout<<"\n\n";
    // for (int i = 0; i < max_stack.size(); ++i)
    // {
    //  cout<<min_stack[i].slope<<" "<<min_stack[i].intercept<<" "<<min_stack[i].stime<<" "<<min_stack[i].ftime<<"\n";
    // }
    // cout<<"\n\n";

    int p1 = 0, p2 = 0;
    double ans = 1e20;
    while(p1 < 2*max_stack.size() && p2 < 2*min_stack.size())
    {
        double t1,t2;
        if(p1 & 1)
            t1 = max_stack[p1/2].ftime;
        else
            t1 = max_stack[p1/2].stime;

        if(p2 & 1)
            t2 = min_stack[p2/2].ftime;
        else
            t2 = min_stack[p2/2].stime;

        double ft = min(t1,t2);
        double v1 = (max_stack[p1/2].slope*ft)+max_stack[p1/2].intercept;
        double v2 = (min_stack[p2/2].slope*ft)+min_stack[p2/2].intercept;
        ans = min(ans, v1-v2);
        if(abs(t1-t2) < eps)
        {
            p1++;
            p2++;
        }
        else if(t1 < t2)
            p1++;
        else
            p2++;
    }
    cout.precision(6);
    cout<<fixed<<ans<<"\n";
    return 0;
}