Advertisement
Guest User

Untitled

a guest
Nov 12th, 2019
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5.  
  6. #pragma GCC optimize("O3")
  7.  
  8. using namespace std;
  9. using namespace __gnu_pbds;
  10.  
  11. #define int long long
  12. #define double long double
  13. #define _ << ' ' <<
  14. #define For(i,z) for(int32_t i=0;i<(z);i++)
  15. #define sqr(a) ((a)*(a))
  16.  
  17. #define pii pair<int, int>
  18. #define x first
  19. #define v second
  20.  
  21. template<typename T>
  22. using orset = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  23.  
  24. template<typename T, typename K> inline void umax(T &a, K b) { a = max(a, (T)b); }
  25. template<typename T, typename K> inline void umin(T &a, K b) { a = min(a, (T)b); }
  26.  
  27. const int32_t N = 1010;
  28. const int INF = 1e16 + 10;
  29. const double EPS = 1e-6;
  30. const int II = 1e9 + 10;
  31. // const int AMOD = 99194853094755497;
  32. // const int MOD = 1e9+123;
  33.  
  34. struct Drb {
  35. int ch, zn;
  36. Drb(int _ch, int _zn) : ch(_ch), zn(_zn){
  37. int g = __gcd(ch, zn);
  38. ch /= g; zn /= g;
  39. }
  40. Drb() {}
  41. bool operator < (const Drb &ot) const {
  42. return (ch*ot.zn < ot.ch*zn);
  43. }
  44. bool operator == (const Drb &ot) const {
  45. return (ch == ot.ch && zn == ot.zn);
  46. }
  47. bool operator <= (const Drb &ot) const {
  48. return (*this < ot || *this == ot);
  49. }
  50. Drb operator + (const Drb &ot) const {
  51. return Drb(ch*ot.zn+ot.ch*zn, zn*ot.zn);
  52. }
  53. };
  54.  
  55. int n, a, b;
  56. vector <pii> ar;
  57. pair<Drb, int> buf[N];
  58.  
  59. int check(int idx) {
  60. Drb da(abs(ar[idx].x - a), ar[idx].v),
  61. db(abs(ar[idx].x - b), ar[idx].v);
  62.  
  63. if (db < da) swap(da, db);
  64. int cur = 0, cc = 0;
  65. buf[cc++] = make_pair(da, 0);
  66. buf[cc++] = make_pair(db, 0);
  67. For (i, n) {
  68. int dv = ar[idx].v - ar[i].v;
  69. int dx = ar[i].x - ar[idx].x;
  70. if (dv == 0) {
  71. if (dx > 0)
  72. cur++;
  73. continue;
  74. }
  75. Drb dt(dx, dv);
  76. if (dx >= 0) {
  77. cur++;
  78. if (dv > 0)
  79. buf[cc++] = make_pair(dt, -1);
  80. } else
  81. if (dv < 0 && dx <= 0)
  82. buf[cc++] = make_pair(dt, 1);
  83. }
  84. sort(buf, buf + cc);
  85. int ans = n-1;
  86. For (tt, cc){
  87. cur += buf[tt].second;
  88. if (da <= buf[tt].first && buf[tt].first <= db)
  89. umin(ans, cur);
  90. }
  91. return ans;
  92. }
  93.  
  94. int32_t main() {
  95. // freopen("input.txt", "r", stdin);
  96. // freopen("output.txt", "w", stdout);
  97. ios_base::sync_with_stdio(false);
  98. cin.tie(0); cout.tie(0);
  99.  
  100. cin >> n >> a >> b;
  101. ar.resize(n);
  102. For (i, n) cin >> ar[i].x >> ar[i].v;
  103.  
  104. For (i, n)
  105. cout << check(i) + 1 << '\n';
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement