Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include<algorithm>
- using namespace std;
- struct Point
- {
- int x, y;
- Point(int x = 0, int y = 0) : x(x), y(y){}
- };
- bool operator == (const Point & a, const Point & b)
- {
- return a.x == b.x && a.y == b.y;
- }
- int INF = 1000*1000*1000;
- Point INF_P(-INF, INF);
- bool cmpX(const Point & a, const Point & b)
- {
- return a.x < b.x || (a.x == b.x && a.y < b.y);
- }
- bool cmpY(const Point & a, const Point & b)
- {
- return a.y < b.y || (a.y == b.y && a.x < b.x);
- }
- bool inside(int pos, const Point & a)
- {
- return a.x <= pos && pos <= a.y;
- }
- bool fullInside(const Point & a, const Point & b)
- {
- return a.x >= b.x && a.y <= b.y;
- }
- bool intersected(const Point & a, const Point & b)
- {
- return max(a.x, b.x) <= min(a.y, b.y);
- }
- struct Map
- {
- int n;
- vector<Point> p;
- Map(int n = 0) : n(n), p(0){}
- void build()
- {
- _build(0, 0, n);
- }
- void _build(bool byY, int l, int r)
- {
- if(l+1 >= r)
- return;
- int mid = (l + r)/2;
- if(byY)
- {
- nth_element(p.begin() + l, p.begin() + mid, p.begin() + r, cmpY);
- }
- else
- {
- nth_element(p.begin() + l, p.begin() + mid, p.begin() + r, cmpX);
- }
- _build(!byY, l, mid);
- _build(!byY, mid + 1, r);
- }
- int getCount(Point X, Point Y)
- {
- return _getCount(0, X, Y, 0, n);
- }
- int _getCount(bool byY, Point X, Point Y, int l, int r)
- {
- if(l >= r)
- return 0;
- if(l + 1 == r)
- return inside(p[l].x, X) && inside(p[l].y, Y);
- if(X == INF_P && Y == INF_P)
- return r - l;
- int mid = (l + r)/2;
- int cnt = inside(p[mid].x, X) && inside(p[mid].y, Y);
- if(byY)
- {
- if(p[mid].y > Y.y)
- {
- cnt += _getCount(!byY, X, Y, l, mid);
- }
- else
- if(p[mid].y < Y.x)
- {
- cnt += _getCount(!byY, X, Y, mid+1, r);
- }
- else
- {
- cnt += _getCount(!byY, X, Point(Y.x, INF), l, mid);
- cnt += _getCount(!byY, X, Point(-INF, Y.y), mid+1, r);
- }
- }
- else
- {
- if(p[mid].x > X.y)
- {
- cnt += _getCount(!byY, X, Y, l, mid);
- }
- else
- if(p[mid].x < X.x)
- {
- cnt += _getCount(!byY, X, Y, mid+1, r);
- }
- else
- {
- cnt += _getCount(!byY, Point(X.x, INF), Y, l, mid);
- cnt += _getCount(!byY, Point(-INF, X.y), Y, mid+1, r);
- }
- }
- return cnt;
- }
- };
- istream & operator >> (istream & in, Point & toRead)
- {
- in >> toRead.x >> toRead.y;
- return in;
- }
- istream & operator >> (istream & in, Map & toRead)
- {
- in >> toRead.n;
- toRead.p.resize(toRead.n);
- for(int i = 0; i<toRead.n; i++)
- in >> toRead.p[i];
- toRead.build();
- return in;
- }
- int main()
- {
- ios::sync_with_stdio(false);
- cin.tie(0);
- Map M;
- cin >> M;
- int q;
- cin >> q;
- while(q--)
- {
- int x1, x2, y1, y2;
- cin >> x1 >> x2 >> y1 >> y2;
- if(x1 > x2)
- swap(x1, x2);
- if(y1 > y2)
- swap(y1, y2);
- cout << M.getCount(Point(x1, x2), Point(y1, y2)) << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement