Submission #4034847


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 {
    if (a.a != b.a) return a.a < b.a;
    return a.b < b.b;
  });
  
  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

Submission Time
Task G - Moving Points
User hs484
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2473 Byte
Status AC
Exec Time 535 ms
Memory 14952 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 18
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 2 ms 256 KB
10 AC 2 ms 256 KB
11 AC 5 ms 384 KB
12 AC 5 ms 384 KB
13 AC 13 ms 640 KB
14 AC 11 ms 512 KB
15 AC 224 ms 9324 KB
16 AC 275 ms 7020 KB
17 AC 171 ms 4464 KB
18 AC 189 ms 5484 KB
2 AC 1 ms 256 KB
3 AC 1 ms 256 KB
4 AC 1 ms 256 KB
5 AC 1 ms 256 KB
6 AC 535 ms 14952 KB
7 AC 2 ms 256 KB
8 AC 2 ms 256 KB
9 AC 1 ms 256 KB