fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //#pragma GCC optimize("Ofast")
  4. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  5.  
  6. #define ms(s, n) memset(s, n, sizeof(s))
  7. #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
  8. #define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
  9. #define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
  10. #define sz(a) int((a).size())
  11. #define present(t, x) (t.find(x) != t.end())
  12. #define all(a) (a).begin(), (a).end()
  13. #define uni(a) (a).erase(unique(all(a)), (a).end())
  14. #define pb push_back
  15. #define pf push_front
  16. #define mp make_pair
  17. #define fi first
  18. #define se second
  19. #define prec(n) fixed<<setprecision(n)
  20. #define bit(n, i) (((n) >> (i)) & 1)
  21. #define bitcount(n) __builtin_popcountll(n)
  22. typedef long long ll;
  23. typedef unsigned long long ull;
  24. typedef long double ld;
  25. typedef pair<int, int> pi;
  26. typedef vector<int> vi;
  27. typedef vector<pi> vii;
  28. const int MOD = (int) 1e9 + 7;
  29. const int FFTMOD = 119 << 23 | 1;
  30. const int INF = (int) 1e9 + 23111992;
  31. const ll LINF = (ll) 1e18 + 23111992;
  32. const ld PI = acos((ld) -1);
  33. const ld EPS = 1e-9;
  34. inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
  35. inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
  36. inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
  37. template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
  38. template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
  39. inline ull isqrt(ull k) {ull r = sqrt(k) + 1; while (r * r > k) r--; return r;}
  40. inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
  41. inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
  42. inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
  43. inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
  44. inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
  45. inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
  46. inline int sign(ld x, ld y) {return sign(x - y);}
  47. mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
  48. inline int mrand() {return abs((int) mt());}
  49. inline int mrand(int k) {return abs((int) mt()) % k;}
  50. #define db(x) cerr << "[" << #x << ": " << (x) << "] ";
  51. #define endln cerr << "\n";
  52.  
  53. struct point_t {
  54.     int x, y;
  55.     point_t(int x = 0, int y = 0) : x(x), y(y) {}
  56.     int operator < (const point_t& rhs) const {return make_pair(y, x) < make_pair(rhs.y, rhs.x);}
  57.     int operator == (const point_t& rhs) const {return make_pair(y, x) == make_pair(rhs.y, rhs.x);}
  58.     point_t operator - (const point_t& rhs) const {return point_t(x - rhs.x, y - rhs.y);}
  59.     point_t operator + (const point_t& rhs) const {return point_t(x + rhs.x, y + rhs.y);}
  60. };
  61. long long cross(point_t a, point_t b) {
  62.     return (long long) a.x * b.y - (long long) a.y * b.x;
  63. }
  64. long long area(point_t a, point_t b, point_t c) {
  65.     return cross(a, b) + cross(b, c) + cross(c, a);
  66. }
  67. long long dist(point_t a, point_t b) {
  68.     return (long long) (a.x - b.x) * (a.x - b.x) + (long long) (a.y - b.y) * (a.y - b.y);
  69. }
  70. point_t RotateCCW90(point_t p) {
  71.     return point_t(-p.y, p.x);
  72. }
  73.  
  74. struct frac_t {
  75.     long long p, q;
  76.     frac_t(long long p = 0, long long q = 1) : p(p), q(q) {}
  77.     friend int operator < (frac_t a, frac_t b) {
  78.         return (__int128) a.p * b.q < (__int128) b.p * a.q;
  79.     }
  80.     void normalize() {
  81.         if (q < 0) {
  82.             p *= -1, q *= -1;
  83.         }
  84.         long long g = __gcd(abs(p), q);
  85.         p /= g, q /= g;
  86.     }
  87.     frac_t operator + (frac_t rhs) {
  88.         frac_t res(p * rhs.q + rhs.p * q, q * rhs.q);
  89.         res.normalize();
  90.         return res;
  91.     }
  92.     frac_t operator - (frac_t rhs) {
  93.         frac_t res(p * rhs.q - rhs.p * q, q * rhs.q);
  94.         res.normalize();
  95.         return res;
  96.     }
  97.     frac_t operator * (frac_t rhs) {
  98.         frac_t res(p * rhs.p, q * rhs.q);
  99.         res.normalize();
  100.         return res;
  101.     }
  102. };
  103.  
  104. void chemthan() {
  105.     int n; cin >> n;
  106.     int x, y; cin >> x >> y;
  107.     int a, b; cin >> a >> b;
  108.     vector<point_t> recs;
  109.     recs.pb({-a / 2, -b / 2});
  110.     recs.pb({+a / 2, -b / 2});
  111.     recs.pb({+a / 2, +b / 2});
  112.     recs.pb({-a / 2, +b / 2});
  113.     vector<point_t> pts(n);
  114.     FOR(i, 0, n) {
  115.         cin >> pts[i].x >> pts[i].y;
  116.         pts[i].x -= x + a / 2;
  117.         pts[i].y -= y - b / 2;
  118.     }
  119.     for (auto& e : recs) e.x *= 2, e.y *= 2;
  120.     for (auto& e : pts) e.x *= 2, e.y *= 2;
  121.     int res = 0;
  122.     FOR(it, 0, 2) {
  123.         swap(a, b);
  124.         for (auto& e : recs) swap(e.x, e.y);
  125.         for (auto& e : pts) swap(e.x, e.y);
  126.         vector<pair<frac_t, int>> events;
  127.         for (auto p : pts) {
  128.             frac_t lo(-b, 1);
  129.             frac_t hi(+b, 1);
  130.             for (auto q : recs) {
  131.                 point_t u = p + q;
  132.                 u.x /= 2, u.y /= 2;
  133.                 point_t v = u + RotateCCW90(p - q);
  134.                 long long tp = cross(u, v);
  135.                 long long tq = u.x - v.x;
  136.                 //point_t w(0, tp);
  137.                 //u.y *= tq, v.y *= tq;
  138.                 //assert(!cross(u - w, v - w));
  139.                 if (tq < 0) {
  140.                     tp *= -1;
  141.                     tq *= -1;
  142.                 }
  143.                 long long g = __gcd(abs(tp), abs(tq));
  144.                 tp /= g, tq /= g;
  145.                 if (q.y < p.y) {
  146.                     chkmin(hi, frac_t(tp, tq));
  147.                 }
  148.                 else if (p.y < q.y) {
  149.                     chkmax(lo, frac_t(tp, tq));
  150.                 }
  151.             }
  152.             if (lo < hi) {
  153.                 events.pb({lo, +1});
  154.                 events.pb({hi, -1});
  155.             }
  156.         }
  157.         sort(all(events));
  158.         int sum = 0;
  159.         FOR(i, 0, sz(events) - 1) {
  160.             sum += events[i].se;
  161.             if (events[i].fi < events[i + 1].fi) {
  162.                 chkmax(res, sum);
  163.             }
  164.         }
  165.     }
  166.     cout << n - res << "\n";
  167. }
  168.  
  169. int main(int argc, char* argv[]) {
  170.     ios_base::sync_with_stdio(0), cin.tie(0);
  171.     if (argc > 1) {
  172.         assert(freopen(argv[1], "r", stdin));
  173.     }
  174.     if (argc > 2) {
  175.         assert(freopen(argv[2], "wb", stdout));
  176.     }
  177.     chemthan();
  178.     cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  179.     return 0;
  180. }
Success #stdin #stdout #stderr 0s 4536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
Time elapsed: 4ms
https://ideone.com/RPXYbK
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!