Pagini recente » Cod sursa (job #930948) | Cod sursa (job #1991428) | Cod sursa (job #1292561) | Cod sursa (job #884433) | Cod sursa (job #2461043)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define x first
#define y second
using namespace std;
const int NMAX = 16001;
const int MMAX = 100001;
typedef pair <int, int> pii;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
int N, M;
pii A[NMAX];
struct zoo
{
int x1, y1, x2, y2;
}Z[NMAX];
int F[MMAX*4 + NMAX*2];
vector < int > C;
int CB( int val, int lf, int rg )
{
int mid = lf + ( rg - lf )/2;
if( F[mid] == val ) return mid;
if( F[mid] > val ) return CB(val, lf, mid - 1);
else return CB( val, mid + 1, rg );
}
void Read()
{
fin >> N;
for( int i = 1; i <= N; ++i )
{
fin >> A[i].x >> A[i].y;
C.push_back( A[i].x );
C.push_back( A[i].y );
}
fin >> M;
for( int i = 1; i <= M; ++i )
{
fin >> Z[i].x1 >> Z[i].y1 >> Z[i].x2 >> Z[i].y2;
C.push_back( Z[i].x1 );
C.push_back( Z[i].y1 );
C.push_back( Z[i].x2 );
C.push_back( Z[i].y2 );
}
sort( C.begin(), C.end());
int val = -2000000001;
for( int i = 0; i < C.size(); ++i )
{
if( C[i] != val )
{
val = C[i];
F[0]++;
F[F[0]] = C[i];
}
}
//for( int i = 1; i <= F[0]; ++i ) fout << i << ' ' << F[i] << '\n';
for( int i = 1; i <= N; ++i )
{
A[i].x = CB( A[i].x, 1, F[0] );
A[i].y = CB( A[i].y, 1, F[0] );
//fout << A[i].x << ' ' << A[i].y << '\n';
}
for( int i = 1; i <= M; ++i )
{
Z[i].x1 = CB( Z[i].x1, 1, F[0]);
Z[i].y1 = CB( Z[i].y1, 1, F[0]);
Z[i].x2 = CB( Z[i].x2, 1, F[0]);
Z[i].y2 = CB( Z[i].y2, 1, F[0]);
//fout << Z[i].x1 << Z[i].y1 << Z[i].x2 << Z[i].y2;
}
}
void Do()
{
for( int i = 1; i <= M; ++i )
{
int nr = 0;
for( int j = 1; j <= N; ++j )
{
if( A[j].x >= Z[i].x1 && A[j].x <= Z[i].x2 && A[j].y >= Z[i].y1 && A[j].y <= Z[i].y2 ) nr++;
}
fout << nr << '\n';
}
}
int main()
{
Read();
Do();
return 0;
}