Submission #4034787

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

struct Line {
  double a;
  double b;
  double f(double x) {
    return a * x + b;
  }
};

// 2 点 (x1, y1), (x2, y2) を通る直線を返す
Line fromPP(double x1, double y1, double x2, double y2) {
  double dx = x2 - x1;
  double dy = y2 - y1;
  double m = (dy / dx);
  return (Line) { m, -m*x1 + y1 };
}

bool check(Line l1, Line l2, Line l3) {
  return (l1.a-l2.a)*(l3.b-l2.b) <= (l2.a-l3.a)*(l2.b-l1.b);
}

int main2() {
  int N, M;
  cin >> N >> M;
   
  vector<Line> ls;
  REP(_, N) {
    double x, y, vx, vy;
    cin >> x >> y >> vx >> vy;

    auto fpp = [=](double t){return  (x + t*vx) + (y + t*vy);};
    auto fpm = [=](double t){return  (x + t*vx) - (y + t*vy);};
    auto fmp = [=](double t){return -(x + t*vx) + (y + t*vy);};
    auto fmm = [=](double t){return -(x + t*vx) - (y + t*vy);};

    ls.push_back(fromPP(0, fpp(0), 1000000, fpp(1000000)));
    ls.push_back(fromPP(0, fpm(0), 1000000, fpm(1000000)));
    ls.push_back(fromPP(0, fmp(0), 1000000, fmp(1000000)));
    ls.push_back(fromPP(0, fmm(0), 1000000, fmm(1000000)));
  }
  sort(ALL(ls), [](const Line&a, const Line&b) -> bool {
    return a.a < b.a;
  });
  
  deque<Line> deq;
  for (Line line : ls) {
    while (deq.size() >= 2 && check(deq[deq.size()-2], deq[deq.size()-1], line))
      deq.pop_back();
    deq.push_back(line);
  }

  vector< pair<double, int> > ts;
  vector<double> ans(M);
  REP(i, M) {
    double t; cin >> t;
    ts.push_back(make_pair(t, i));
  }
  sort(ALL(ts));
  for (auto ti : ts) {
    double t = ti.first;
    int index = ti.second;

    while (deq.size() >= 2 && deq[0].f(t) <= deq[1].f(t)) deq.pop_front();
    double val = deq.size() >= 1 ? deq[0].f(t) : 0;

    ans[index] = val;
  }
  REP(i, M)
    printf("%.10f\n", ans[i]);
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}

Submission Info

Judge Result