Pagini recente » Cod sursa (job #2321464) | Cod sursa (job #1220653) | Rating Badulescu Andrei Catalin (BadulescuCatalin) | Cod sursa (job #2336270) | Cod sursa (job #159215)
Cod sursa(job #159215)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
enum {START, POINT, END};
const int MAX_COORD = 1000000;
const int MAX_DIM = 2097152;
class event
{
public:
char type;
int x, y;
bool operator < (const event &A) const
{
if(x != A.x)
return x < A.x;
if(type != A.type)
return type < A.type;
return y < A.y;
}
};
int N, M, W, H;
vector <event> E;
int cnt = 0;
bool T[MAX_DIM];
int A, B;
void read_data()
{
event tmp;
ifstream in("ograzi.in");
in >> N >> M >> W >> H;
for(int i = 0; i < N; ++i)
{
tmp.type = START;
in >> tmp.x >> tmp.y;
E.push_back(tmp);
tmp.type = END;
tmp.x += W;
E.push_back(tmp);
}
for(int i = 0; i < M; ++i)
{
tmp.type = POINT;
in >> tmp.x >> tmp.y;
E.push_back(tmp);
}
}
void mark(int n, int lo, int hi, const bool &value)
{
if(A <= lo && hi <= B)
{
T[n] = value;
return;
}
if(A <= (lo + hi) / 2)
mark(2 * n, lo, (lo + hi) / 2, value);
if(B > (lo + hi) / 2)
mark(2 * n + 1, (lo + hi) / 2 + 1, hi, value);
}
bool query(int n, int lo, int hi, const int &p)
{
if(T[n])
return true;
if(lo == hi)
return false;
if(p <= (lo + hi) / 2)
return query(2 * n, lo, (lo + hi) / 2, p);
else
return query(2 * n + 1, (lo + hi) / 2 + 1, hi, p);
}
void solve()
{
for(size_t i = 0; i < E.size(); ++i)
switch(E[i].type)
{
case START:
A = E[i].y;
B = E[i].y + H;
mark(1, 0, MAX_COORD, true);
break;
case END:
A = E[i].y;
B = E[i].y + H;
mark(1, 0, MAX_COORD, false);
break;
default:
cnt += query(1, 0, MAX_COORD, E[i].y);
break;
}
}
int main()
{
read_data();
sort(E.begin(), E.end());
solve();
ofstream out("ograzi.out");
out << cnt << endl;
return 0;
}