MRECT1 - Điểm trên cạnh hình chữ nhật - HRASTOVI
Tác giả: ladpro98
Ngôn ngữ: C++
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
//#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it)
#define RESET(a, v) memset((a), (v), sizeof((a)))
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 700005;
using namespace std;
int n, m, p;
int x1[N], y1[N], x2[N], y2[N];
struct point {
int x, y, id;
point(int _x = 0, int _y = 0, int _id = 0) {
x = _x; y = _y; id = _id;
}
bool operator < (const point &b) const {
return (x != b.x) ? (x < b.x) : ((y != b.y) ? (y < b.y) : id < b.id);
}
} a[N];
int findLeft(point a) {
if (a.y == y1[a.id]) return -1;
return y1[a.id];
}
int s[N];
int ans[N];
void solve() {
sort(a + 1, a + 1 + p);
int j;
for(int i = 1; i <= p; i = j + 1) {
j = i;
while (a[j + 1].x == a[i].x) j++;
s[i - 1] = 0;
REP(k, i, j) {
s[k] = s[k - 1];
if (a[k].id) {
int l = i, r = k, pos;
int leftBound = findLeft(a[k]);
if (leftBound == -1) continue;
while (l <= r) {
int mid = l + r >> 1;
if (a[mid].y >= leftBound) {
pos = mid; r = mid - 1;
}
else
l = mid + 1;
}
ans[a[k].id] += s[k] - s[pos - 1];
}
else
s[k]++;
}
}
}
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> n;
REP(i, 1, n) cin >> a[i].x >> a[i].y;
cin >> m;
p = n;
REP(i, 1, m) {
cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
a[++p] = point(x1[i], y1[i], i);
a[++p] = point(x1[i], y2[i], i);
a[++p] = point(x2[i], y1[i], i);
a[++p] = point(x2[i], y2[i], i);
}
solve();
REP(i, 1, p) swap(a[i].x, a[i].y);
REP(i, 1, m) {
int yy1 = y1[i], yy2 = y2[i];
y1[i] = x1[i]; y2[i] = x2[i];
x1[i] = yy2; x2[i] = yy1;
}
solve();
int j;
for(int i = 1; i <= p; i = j + 1) {
j = i;
if (a[i].id == 0) {
while (a[j + 1].x == a[i].x && a[j + 1].y == a[i].y)
ans[a[++j].id]--;
}
}
REP(i, 1, m) cout << ans[i] << '\n';
return 0;
}