Pagini recente » panamasum | Profil Gaspar_Stefan | Rating Croitoru Gabriel (LtRaven) | Cod sursa (job #3137946) | Cod sursa (job #3261490)
#include <bits/stdc++.h>
#define inf INT_MAX
using namespace std;
const int nmax = 16000;
struct ura
{
int a, b;
}v[nmax + 1];
int l[nmax + 1], c[nmax + 1];
bool cmp1(ura a, ura b)
{
return a.a < b.b;
}
bool cmp2(ura a, ura b)
{
return a.b < b.b;
}
int cbs(int v[], int n, int val)
{
int st = 1, dr = n, poz, mij;
while(st <= dr)
{
mij = (st + dr) / 2;
if(v[mij] <= val)
{
poz = mij;
dr = mij - 1;
}
else
st = mij + 1;
}
return v[poz];
}
int cbd(int v[], int n, int val)
{
int st = 1, dr = n, poz, mij;
while(st <= dr)
{
mij = (st + dr) / 2;
if(v[mij] >= val)
{
poz = mij;
dr = mij - 1;
}
else
st = mij + 1;
}
return v[poz];
}
int main()
{
freopen("zoo.in", "r", stdin);
freopen("zoo.out", "w", stdout);
ios :: sync_with_stdio(false);
cin.tie(0);
int n,i;
l[0] = inf;
memset(l, inf, n);
memset(c, inf, n);
cin >> n;
for(i = 1; i <= n; i++)
{
cin >> v[i].a >> v[i].b;
}
sort(v + 1, v + n + 1, cmp1);
for(i=1 ; i <= n; i++)
{
if(v[i].a != l[v[i - 1].a])
{
l[v[i-1].a + 1] = v[i].a;
v[i].a = v[i - 1].a + 1;
}
}
sort(v + 1, v + n + 1, cmp2);
for(i=1 ; i <= n; i++)
{
if(v[i].b != c[v[i - 1].b])
{
c[v[i-1].b + 1] = v[i].b;
v[i].b = v[i - 1].b + 1;
}
}
int q, x1, x2, y1, y2;
cin >> q;
while(q > 0)
{
q--;
cin >> x1 >> y1 >> x2 >> y2;
x1 = cbd(l, n, x1);
x2 = cbs(l, n, x2);
y1 = cbd(c, n, y1);
y2 = cbs(c, n, y2);
}
return 0;
}