Submission #159378

#	Time	Username	Problem	Language	Result	Execution time	Memory
159378		exqt	Jogging (kriii1_J)	C++14	0 / 1	102 ms	8328 KiB

J

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

using ll = long long;
using pii = pair<ll, ll>;

struct Line {
  ll x, y; // (xi - x) / yi

  double cross(Line &o) {
    double t = 1.0 * (x*o.y - o.x*y) / (o.y - y + 1e-18);
    return t;
  }

  double eval(double p) {
    return 1.0 * (x - p) / y;
  }
};

int main(int argc, char **argv) {
#ifdef LOCAL
  freopen("in.txt", "r", stdin);
#endif
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int n, m; cin >> n >> m;
  vector<Line> linesT(n);
  for(int i=0; i<n; i++) {
    cin >> linesT[i].x >> linesT[i].y;
  }

  vector<int> qrys(m);
  for(int i=0; i<m; i++) cin >> qrys[i];

  sort(linesT.begin(), linesT.end(), [&](Line &a, Line &b) {
    if(a.x != b.x) return a.x < b.x;
    else return a.y > b.y;
  });

  vector<Line> lines;
  for(Line l : linesT) {
    if(lines.size() == 0 || lines.back().x != l.x)
      lines.push_back(l);
  }

  vector<double> res(m);
  vector<Line> st;
  for(int i=m-1; i>=0; i--) {
    while(lines.size() && qrys[i] < lines.back().x) {
      while(st.size()) {
        double c = st.back().cross(lines.back());
        if(st.back().eval(qrys[i]) >= lines.back().eval(qrys[i]) && qrys[i] < c)
          st.pop_back();
        else break;
      }

      st.push_back(lines.back());
      lines.pop_back();
    }

    while(st.size() >= 2 &&
    qrys[i] <= st[(int)st.size()-2].cross(st.back())) {
      st.pop_back();
    }

    res[i] = (st.size() ? st.back().eval(qrys[i]) : -1.0);
  }

  cout << fixed;
  cout.precision(7);
  for(double r : res) cout << (r == -1.0 ? 0.0 : atan(1.0/r)) << '\n';

  return 0;
}

• Subtask 1: 0 / 1