Submission #4034690

---

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);
}

const double EPS = 1e-9;
bool isZero(double x) {
  return abs(x) < EPS;
}

const int MAX_M = 112345;
double ans[MAX_M];

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

    auto f = [=](double t){
      return abs(x + t*vx) + abs(y + t*vy);
    };

    if (isZero(vx) && isZero(vy)) {
      constant = max(constant, (x + y));
    } else if (isZero(vx) || isZero(vy)) {
      if (isZero(vx)) {
        swap(x, y);
        swap(vx, vy);
      }
      // assert(vx != 0 && vy == 0);
      double t1 = (double) -x / vx;
      Line l1 = fromPP(t1-1, f(t1-1), t1, f(t1));
      Line l2 = fromPP(t1, f(t1), t1+1, f(t1+1));
      ls.push_back(l1);
      ls.push_back(l2);
    } else {
      double t1 = (double) -x / vx;
      double t2 = (double) -y / vy;
      if (isZero(t1 - t2)) {
        Line l1 = fromPP(t1-1, f(t1-1), t1, f(t1));
        Line l2 = fromPP(t1, f(t1), t1+1, f(t1+1));
        ls.push_back(l1);
        ls.push_back(l2);
      } else {
        if (t1 > t2) {
          swap(t1, t2);
          swap(x, y);
          swap(vx, vy);
        }
        Line l1 = fromPP(t1-1, f(t1-1), t1, f(t1));
        Line l2 = fromPP(t1, f(t1), t2, f(t2));
        Line l3 = fromPP(t2, f(t2), t2+1, f(t2+1));
        ls.push_back(l1);
        ls.push_back(l2);
        ls.push_back(l3);
      }
    }
  }
  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;
  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) : -9999999;

    val = max(val, constant);
    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