Submission #103081


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,-1e5});
    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;
        double ans = 0;
        auto it = upper_bound(all(ti),pair<double,int>{t-EPS,-1});
        //cout << (*it).first << " " << (*it).second << endl;
        it--;
        printf("%.12f\n",f(vl[(*it).second],t));
    }
}

Submission Info

Submission Time
Task G - Moving Points
User YellowYell
Language C++11 (GCC 4.8.1)
Score 0
Code Size 2766 Byte
Status WA
Exec Time 1435 ms
Memory 15380 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 16
WA × 2
Set Name Test Cases
All 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 2, 3, 4, 5, 6, 7, 8, 9
Case Name Status Exec Time Memory
1 AC 24 ms 796 KB
10 AC 23 ms 796 KB
11 AC 32 ms 920 KB
12 AC 29 ms 1048 KB
13 AC 67 ms 1072 KB
14 AC 47 ms 1068 KB
15 WA 402 ms 5668 KB
16 WA 652 ms 9616 KB
17 AC 806 ms 2680 KB
18 AC 451 ms 5404 KB
2 AC 22 ms 792 KB
3 AC 22 ms 800 KB
4 AC 20 ms 924 KB
5 AC 24 ms 808 KB
6 AC 1435 ms 15380 KB
7 AC 22 ms 928 KB
8 AC 24 ms 928 KB
9 AC 23 ms 796 KB