Pagini recente » Cod sursa (job #3176930) | Cod sursa (job #35720) | Cod sursa (job #3613) | Cod sursa (job #2252771) | Cod sursa (job #3164557)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
struct dreapta
{
int x1;
int y1;
int x2;
int y2;
};
const int NMAX = 16007;
const int MMAX = 1e5 + 7;
pair<int, int> p[NMAX];
vector<dreapta> d(MMAX);
int sol, k;
int s[MMAX * 5];
vector<int> v[5 * MMAX];
void build(int nod, int st, int dr)
{
for (int i = st; i <= dr; i++)
{
v[nod].push_back(p[i].second);
}
sort(v[nod].begin(), v[nod].end());
if (st < dr)
{
int mid = (st + dr) / 2;
build(2 * nod, st, mid);
build(2 * nod + 1, mid + 1, dr);
}
}
int cautaPrimul(int x, int nod)
{
int st = 0;
int dr = v[nod].size() - 1;
while (st <= dr)
{
int mid = (st + dr) / 2;
if (v[nod][mid] >= x)
dr = mid - 1;
else
st = mid + 1;
}
return st;
}
int cautaUltimul(int x, int nod)
{
int st = 0;
int dr = v[nod].size() - 1;
while (st <= dr)
{
int mid = (st + dr) / 2;
if (v[nod][mid] <= x)
st = mid + 1;
else
dr = mid - 1;
}
return dr;
}
int cauta(int x)
{
int st = 0;
int dr = k - 1;
while (st <= dr)
{
int mid = (st + dr) / 2;
if (s[mid] == x)
return mid;
else if (x < s[mid])
dr = mid - 1;
else
st = mid + 1;
}
}
void query(int nod, int st, int dr, int poz)
{
if (st > dr)
return;
if (d[poz].x1 <= p[st].first && d[poz].x2 >= p[dr].first)
sol += (cautaUltimul(d[poz].y2, nod) - cautaPrimul(d[poz].y1, nod) + 1);
else
{
if (st == dr)
return;
int mid = (st + dr) / 2;
if (d[poz].x1 <= p[mid].first)
query(2 * nod, st, mid, poz);
if (d[poz].x2 >= p[mid + 1].first)
query(2 * nod + 1, mid + 1, dr, poz);
}
}
int main()
{
int n, m;
fin >> n;
for (int i = 1; i <= n; i++)
{
fin >> p[i].first >> p[i].second;
s[k++] = p[i].first;
s[k++] = p[i].second;
}
fin >> m;
for (int i = 1; i <= m; i++)
{
fin >> d[i].x1 >> d[i].y1 >> d[i].x2 >> d[i].y2;
s[k++] = d[i].x1;
s[k++] = d[i].y1;
s[k++] = d[i].x2;
s[k++] = d[i].y2;
}
sort(s, s + k);
int last = 0;
for (int i = 1; i < k; i++)
{
if (s[i] != s[last])
{
s[++last] = s[i];
}
}
k = last + 1;
for (int i = 1; i <= n; i++)
{
p[i].first = cauta(p[i].first);
p[i].second = cauta(p[i].second);
}
for (int i = 1; i <= m; i++)
{
d[i].x1 = cauta(d[i].x1);
d[i].y1 = cauta(d[i].y1);
d[i].x2 = cauta(d[i].x2);
d[i].y2 = cauta(d[i].y2);
}
sort(p + 1, p + n + 1);
build(1, 1, n);
for (int i = 1; i <= m; i++)
{
sol = 0;
query(1, 1, n, i);
fout << sol << "\n";
}
return 0;
}