Submission #102493

---

Source Code Expand

#include <bits/stdc++.h>
#define iter(i,s,n) for(int i=int(s);i<int(n);i++)
#define rep(i,n)    iter(i,0,n)
#define all(c)      (c).begin(), (c).end()
using namespace std;

typedef pair<double,double> pdd;

const double EPS = 1e-9;
double f(const pdd &l,double t){return l.first*t + l.second;}
double px(const pdd &A,const pdd &B){return (B.second-A.second)/(A.first-B.first);}

int main(){
    int n,m;
    vector<pair<double,double>> tmp, vl;

    cin >> n >> m;
    rep(i,n){
        double x,y,u,v;
        cin >> x >> y >> u >> v;
        tmp.push_back({ u+v, x+y});
        tmp.push_back({ u-v, x-y});
        tmp.push_back({-u+v,-x+y});
        tmp.push_back({-u-v,-x-y});
    }
    sort(all(tmp),[](const pdd &A, const pdd &B){
            if(A.first < B.first) return true;
            if(A.first > B.first) return false;
            return A.second > B.second;
            });


    vl.push_back({-1e9,-1e-5});
    vl.push_back(tmp[0]);
    iter(i,1,4*n){
        if(abs(tmp[i].first - tmp[i-1].first) > EPS) vl.push_back(tmp[i]);
    }

    vector<pair<double,int>> ti;
    ti.push_back({-1,0});
    for(int i = 1; i < vl.size(); i++){
        double t;
        while(1){
            int tail = ti.size()-1;
            t = px(vl[ti[tail].second],vl[i]);
            if(t > ti[tail].first) break;
            ti.pop_back();
        }
        ti.push_back({t,i});
    }

    rep(i,m){
        double t;
        cin >> t;
        auto it = upper_bound(all(ti),pair<double,int>{t-EPS,-1});
        it--;
        printf("%.12f\n",f(vl[(*it).second],t));
    }

}

Submission Info

Judge Result