Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #pragma GCC optimize("O3")
- using namespace std;
- using namespace __gnu_pbds;
- #define int long long
- #define double long double
- #define _ << ' ' <<
- #define For(i,z) for(int32_t i=0;i<(z);i++)
- #define sqr(a) ((a)*(a))
- #define pii pair<int, int>
- #define x first
- #define v second
- template<typename T>
- using orset = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- template<typename T, typename K> inline void umax(T &a, K b) { a = max(a, (T)b); }
- template<typename T, typename K> inline void umin(T &a, K b) { a = min(a, (T)b); }
- const int32_t N = 1010;
- const int INF = 1e16 + 10;
- const double EPS = 1e-6;
- const int II = 1e9 + 10;
- // const int AMOD = 99194853094755497;
- // const int MOD = 1e9+123;
- struct Drb {
- int ch, zn;
- Drb(int _ch, int _zn) : ch(_ch), zn(_zn){
- int g = __gcd(ch, zn);
- ch /= g; zn /= g;
- }
- Drb() {}
- bool operator < (const Drb &ot) const {
- return (ch*ot.zn < ot.ch*zn);
- }
- bool operator == (const Drb &ot) const {
- return (ch == ot.ch && zn == ot.zn);
- }
- bool operator <= (const Drb &ot) const {
- return (*this < ot || *this == ot);
- }
- Drb operator + (const Drb &ot) const {
- return Drb(ch*ot.zn+ot.ch*zn, zn*ot.zn);
- }
- };
- int n, a, b;
- vector <pii> ar;
- pair<Drb, int> buf[N];
- int check(int idx) {
- Drb da(abs(ar[idx].x - a), ar[idx].v),
- db(abs(ar[idx].x - b), ar[idx].v);
- if (db < da) swap(da, db);
- int cur = 0, cc = 0;
- buf[cc++] = make_pair(da, 0);
- buf[cc++] = make_pair(db, 0);
- For (i, n) {
- int dv = ar[idx].v - ar[i].v;
- int dx = ar[i].x - ar[idx].x;
- if (dv == 0) {
- if (dx > 0)
- cur++;
- continue;
- }
- Drb dt(dx, dv);
- if (dx >= 0) {
- cur++;
- if (dv > 0)
- buf[cc++] = make_pair(dt, -1);
- } else
- if (dv < 0 && dx <= 0)
- buf[cc++] = make_pair(dt, 1);
- }
- sort(buf, buf + cc);
- int ans = n-1;
- For (tt, cc){
- cur += buf[tt].second;
- if (da <= buf[tt].first && buf[tt].first <= db)
- umin(ans, cur);
- }
- return ans;
- }
- int32_t main() {
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- ios_base::sync_with_stdio(false);
- cin.tie(0); cout.tie(0);
- cin >> n >> a >> b;
- ar.resize(n);
- For (i, n) cin >> ar[i].x >> ar[i].v;
- For (i, n)
- cout << check(i) + 1 << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement