Submission #159474

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
159474	2019-10-22T21:54:41 Z	exqt	Jogging (kriii1_J)	C++14	1 / 1	104 ms	6520 KB

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.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	3576 KB	Output is correct
2	Correct	95 ms	6520 KB	Output is correct
3	Correct	95 ms	5968 KB	Output is correct
4	Correct	104 ms	5532 KB	Output is correct
5	Correct	54 ms	3420 KB	Output is correct
6	Correct	54 ms	3532 KB	Output is correct
7	Correct	55 ms	3320 KB	Output is correct
8	Correct	54 ms	3320 KB	Output is correct
9	Correct	56 ms	3448 KB	Output is correct
10	Correct	56 ms	3448 KB	Output is correct
11	Correct	59 ms	3448 KB	Output is correct
12	Correct	55 ms	3320 KB	Output is correct
13	Correct	53 ms	3192 KB	Output is correct
14	Correct	57 ms	3192 KB	Output is correct
15	Correct	60 ms	3192 KB	Output is correct
16	Correct	56 ms	3256 KB	Output is correct