Submission #4034738


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

    Line l1 = fromPP(0, fpp(0), 1, fpp(1));
    Line l2 = fromPP(0, fpm(0), 1, fpm(1));
    Line l3 = fromPP(0, fmp(0), 1, fmp(1));
    Line l4 = fromPP(0, fmm(0), 1, fmm(1));
    ls.push_back(l1);
    ls.push_back(l2);
    ls.push_back(l3);
    ls.push_back(l4);
  }
  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) : 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 0
Code Size 2564 Byte
Status WA
Exec Time 528 ms
Memory 13800 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 1 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 216 ms 9196 KB
16 AC 269 ms 6892 KB
17 WA 166 ms 4464 KB
18 AC 186 ms 6000 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 528 ms 13800 KB
7 AC 2 ms 256 KB
8 AC 2 ms 256 KB
9 WA 1 ms 256 KB