Submission #103078

---

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;
        double X,Y,U,V;
        cin >> x >> y >> u >> v;
        X = abs(x); Y = abs(y); U = abs(u); V = abs(v);
        if(U > V){
            swap(X,Y); swap(U,V);
            swap(x,y); swap(u,v);
        }

        if(V < EPS) {
            tmp.push_back({0.0,X+Y});
        } else if (U < EPS){
            double ty = -y/v;
            tmp.push_back({-V,X+ty*V});
            tmp.push_back({+V,X-ty*V});
        } else {
            double tx = -x/u;
            double ty = -y/v;
            if(tx > ty){
                swap(tx,ty);
                swap(X,Y); swap(U,V);
                swap(x,y); swap(u,v);
            }
            tmp.push_back({-U-V,abs(y+tx*v)-tx*(-U-V)});
            tmp.push_back({+U-V,abs(y+tx*v)-tx*(+U-V)});
            tmp.push_back({+U+V,abs(x+ty*u)-ty*(+U+V)});
        }
    }
    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;
            });

    //rep(i,tmp.size()){ cout << tmp[i].first << " " << tmp[i].second << endl; }


    vl.push_back({-1e9,-1e-5});
    rep(i,tmp.size()){
        if(abs(vl[vl.size()-1].first - tmp[i].first) > EPS) vl.push_back(tmp[i]);
    }

    //puts("-----");
    //rep(i,vl.size()) cout << i << " " << vl[i].first << " " << vl[i].second << endl;
    //puts("-----");

    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;
            //int tail2 = tail-1;
            //if(tail2 < 0) break;
            t = px(vl[ti[tail].second],vl[i]);
            if(t > ti[tail].first) break;
            ti.pop_back();
        }
        ti.push_back({t,i});
    }

    //puts("-----");
    //rep(i,ti.size()) cout << ti[i].first << " " << ti[i].second << endl;
    //puts("-----");

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

}

Submission Info

Judge Result