Segment Drawing

上个月和队友打了MCPC。其中这道题当时感觉不难很快就过了，结果别的队过的不是很多，可能还是比较有意思吧！挂在这里。

https://mcpc23.kattis.com/contests/mcpc23/problems/segmentdrawing

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define f first
#define s second
typedef long long ll;
int n;
double ans = 0;
ll x[100010], y[100010], l[100010], r[100010];
double minx[100010], maxx[100010];

int main() {
    cin>>n;
    for(int i=0;i<n;i++) {
        cin>>x[i]>>y[i]>>l[i]>>r[i];
    }

    stack<pii> S;

    for(int i=0;i<n;i++) {
        minx[i] = -1e9;
        while(S.size() && S.top().s < y[i]) {
            pii c = S.top();
            S.pop();
            if(x[i] * (y[i] - c.s) + (c.f - x[i]) * y[i] > r[i] * (y[i] - c.s)) {
                cout<<-1<<endl;
                return 0;
            }
            double cx = x[i] + 1.0 * (c.f - x[i]) / (y[i] - c.s) * y[i];
            minx[i] = max(minx[i], cx);
        }
        S.push(make_pair(x[i],y[i]));
    }
    while(!S.empty())S.pop();

    for(int i=n-1;i>=0;i--) {
        maxx[i] = 1e9;
        while(S.size() && S.top().s < y[i]) {
            pii c = S.top();
            S.pop();
            if(x[i] * (y[i] - c.s) + (c.f - x[i]) * y[i] < l[i] * (y[i] - c.s)) {
                cout<<-1<<endl;
                return 0;
            }
            double cx = x[i] + 1.0 * (c.f - x[i]) / (y[i] - c.s) * y[i];
            maxx[i] = min(maxx[i], cx);
        }
        S.push(make_pair(x[i],y[i]));
    }

    cout<<setprecision(15)<<fixed;
    const double eps = 1e-6;
    for(int i=0;i<n;i++){
        minx[i] = max(minx[i], (double)l[i]);
        maxx[i] = min(maxx[i], (double)r[i]);
        if(minx[i] > maxx[i] + eps) {
            cout<<-1<<endl;
            return 0;
        }

        if(minx[i] > x[i]) {
            ans += sqrt(1.0*y[i]*y[i] + 1.0*(minx[i]-x[i])*(minx[i]-x[i]));
        } else if (maxx[i] < x[i]) {
            ans += sqrt(1.0*y[i]*y[i] + 1.0*(maxx[i]-x[i])*(maxx[i]-x[i]));
        } else {
            ans += y[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}