Advertisement
Guest User

Untitled

a guest
Mar 28th, 2020
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define SEND
  5. #define ld long double
  6. #define pb push_back
  7. #define f first
  8. #define s second
  9. mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
  10.  
  11. struct point {
  12. ld x, y, k;
  13. };
  14.  
  15. ld get_k(ld x1, ld y1, ld x2, ld y2) {
  16. if (x1 == x2)return 0;
  17. return (y1 - y2) / (x1 - x2);
  18. }
  19.  
  20. signed main() {
  21. ios::sync_with_stdio(0);
  22. cin.tie(0);
  23. #ifdef SEND
  24. freopen("mountain.in", "r", stdin);
  25. freopen("mountain.out", "w", stdout);
  26. #endif
  27. int n, q;
  28. cin >> n >> q;
  29. point p[n + 1];
  30. ld a = 0, b = 0;
  31. for (int i = 0; i < n; ++i) {
  32. ld d, k;
  33. cin >> d >> k;
  34. p[i] = {a, b, k};
  35. a += d;
  36. b += d * k;
  37. }
  38. p[n] = {a, b, 0};
  39. while (q--) {
  40. ld x, y;
  41. cin >> x >> y;
  42. int pos = 0;
  43. for (int i = 0; i < n + 1; ++i) {
  44. if (p[i].x <= x)pos = i;
  45. }
  46. int pos1 = pos;
  47. if (pos1 < n)pos1++;
  48. pos--;
  49. while (pos >= 0 && get_k(p[pos].x, p[pos].y, x, y) >= p[pos].k) {
  50. pos--;
  51. }
  52. ld ans1 = p[pos + 1].x;
  53. while (pos1 < n && get_k(p[pos1].x, p[pos1].y, x, y) <= p[pos1].k) {
  54. pos1++;
  55. }
  56. ld ans2 = p[pos1].x;
  57. cout << ans1 << " " << ans2 << endl;
  58. }
  59. return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement