Submission #159474

#	Time	Username	Problem	Language	Result	Execution time	Memory
159474		exqt	Jogging (kriii1_J)	C++14	1 / 1	104 ms	6520 KiB

J

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

using ll = long long;

struct Pt {
  int x, y;
  Pt() {}
  Pt(int x, int y) : x(x), y(y) {}

  bool operator<(const Pt &o) const {
    return x < o.x;
  }
  double look_from(int p) {
    return atan2(y, x-p);
  }
};

ll ccw(Pt a, Pt b, Pt c) {
  int abx = b.x - a.x;
  int aby = b.y - a.y;
  int bcx = c.x - b.x;
  int bcy = c.y - b.y;
  return 1LL*abx*bcy - 1LL*aby*bcx;
}

int main () {
#ifdef LOCAL
  freopen("in.txt", "r", stdin);
#endif
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed;
  cout.precision(7);

  int n, m; cin >> n >> m;
  vector<Pt> pts(n);
  for(int i=0; i<n; i++) cin >> pts[i].x >> pts[i].y;
  vector<int> p(m);
  vector<double> res(m);
  for(int i=0; i<m; i++) cin >> p[i];

  sort(pts.begin(), pts.end());

  vector<Pt> st;

  auto upd = [&](int px, int py) {
    while(st.size() >= 2 && ccw(Pt(px, py), st.back(), st[(int)st.size()-2]) >= 0) {
      st.pop_back();
    }
  };

  for(int i=m-1; i>=0; i--) {
    while(pts.size() && p[i] < pts.back().x) {
      while(st.size() && pts.back().y >= st.back().y) {
        st.pop_back();
      }

      upd(pts.back().x, pts.back().y);
      st.push_back(pts.back());
      pts.pop_back();
    }

    upd(p[i], 0);
    res[i] = st.size() ? st.back().look_from(p[i]) : 0.0;
  }

  for(int i=0; i<m; i++) {
    cout << res[i] << '\n';
  }

  return 0;
}

• Subtask 1: 1 / 1