Pagini recente » Cod sursa (job #1565915) | Cod sursa (job #9075) | Cod sursa (job #6735) | Cod sursa (job #3254294) | Cod sursa (job #3164507)
#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define DIMN 16010
#define DIMM 100010
using namespace std;
struct drept{
int x1;
int y1;
int x2;
int y2;
};
pair<int, int> p[DIMN];
drept d[DIMM];
int n, m, i, sol, k;
int s[DIMM*5];
vector<int> A[5*DIMM];
/**
La aceasta problema special este ca nodurile arborelui de intervale contin
efectiv copii ale punctelor pe care intervalul respectiv le reprezinta
adica in noduri avem chiar vectori cu y ai punctelor respective
**/
void build(int nod, int st, int dr) {
for (int i=st;i<=dr;i++) {
A[nod].push_back(p[i].second);
}
sort(A[nod].begin(), A[nod].end());
if (st < dr) {
int mid = (st+dr)/2;
build(2*nod, st, mid);
build(2*nod+1, mid+1, dr);
}
}
/**
constructia nodurir din AINT se face de sus in jos cu informatii provenite din vectorul sortat dupa x p.
acest vector nu se modifica, asta ne asigura ca la constructie, pentru 2 fii ai aceluiasi nod
punctele din nodul stang vor avea toate x-ii mai mici dau egali decat toate punctele din fiul drept
Apoi, toate aceste puncte din fii se sorteaza intyre ele dupa y.
**/
void build_aux(int nod, int st, int dr) {
if (st == dr) {
A[nod].push_back(p[st].second);
}
if (st < dr) {
int mid = (st+dr)/2;
build_aux(2*nod, st, mid);
build_aux(2*nod+1, mid+1, dr);
/**
daca A[2*nod] este vectorul cu punctele din stanga sortate
si daca A[2*nod + 1] este vectorul cu punctele din dreapta sortate
pot interclasa cei 2 vectori in A[nod] si voi obtine punctele din nod
sortate. Astfel castig un "log" care la varianta anterioara apare de la sortare
**/
}
}
int cauta_primul (int y, int nod) {
int st = 0;
int dr = A[nod].size()-1;
while (st <= dr) {
int mid = (st+dr)/2;
if (A[nod][mid] >= y)
dr = mid-1;
else
st = mid+1;
}
return st;
}
int cauta_ultimul (int y, int nod) {
int st = 0;
int dr = A[nod].size()-1;
while (st <= dr) {
int mid = (st+dr)/2;
if (A[nod][mid] <= y)
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;
/**
punctele din p sunt sortate dupa x
inseamna ca p[st].first este x-ul minim al unui punct
dintre cele care au valorile y puse in A[nod]
iar p[st].first este x-ul maxim al unui punct
dintre cele care au valorile y puse in A[nod]
**/
if(d[poz].x1 <= p[st].first && d[poz].x2 >=p[dr].first) {
/// este un interval din AINT care are toti x-ii punctelor inclusi
/// intre x staga si x dreapta ai dreptunghiului
/// si ramane sa mai interesez doar care (cate) dintre aceste puncte au si
/// y cuprinsi intre ai dreptunghiului
/// de aceea am punctele sortate in nod dupa y ca sa pot cauta binar prima
/// aparitie in A[nod] a unei valori mai mari sau egala cu y de jos al dreptunghiului
/// si ultima aparitie <= y de sus
sol += (cauta_ultimul(d[poz].y2, nod) - cauta_primul(d[poz].y1, nod) + 1);
} else {
if (st == dr)
return;
int mid = (st + dr) / 2;
/// ma gandesc ce s-ar intampla la autoapel in fii:
/// - punctul p[mid] ar fi in fiul stang
/// - punctul p[mid+1] ar fi in fiul drept
if (d[poz].x1 <= p[mid].first) /// daca x din stanga al dreptunghiului este mai mic sau egal decat x-ul celui mai din dreapta nod din fiul stang atunci are sens sa mai caut puncte in stanga
query(2*nod, st, mid, poz);
if (d[poz].x2 >= p[mid+1].first) /// daca x din dreapta al dreptunghiului este mai mare sau egal decat x-ul celui mai din stanga nod din fiul drept atunci are sens sa mai caut puncte in dreapta
query(2*nod+1, mid+1, dr, poz);
}
}
int main () {
ifstream fin ("zoo.in");
ofstream fout("zoo.out");
fin>>n;
for (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 (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 (i=1;i<k;i++) {
if (s[i] != s[last]) {
s[++last] = s[i];
}
}
k = last+1;
/// pana aici s este un vector cu toate coordonatele punctelor, sortat si
/// fara dubluri
for (i=1;i<=n;i++) {
p[i].first = cauta (p[i].first);
p[i].second = cauta (p[i].second);
}
for (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);
}
/**
for (i=1;i<=n;i++) {
cout<<p[i].first<<" "<<p[i].second<<"\n";
}
for (i=1;i<=m;i++) {
cout<<d[i].x1<<" "<<d[i].y1<<" "<<d[i].x2<<" "<<d[i].y2<<"\n";
}
**/
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;
}