Cod sursa(job #1750591)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 30 august 2016 15:51:23
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.26 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAXN 16064
#define MAXM 100050
#define DIM 300000

using namespace std;

struct punct
{
    int x, y;
    punct(int x = 0, int y = 0) : x(x), y(y) { }
};
int n, m, cursor;
char buf[DIM];
punct mat[MAXN];
punct drlo[MAXM], drhi[MAXM];

char getChar()
{
    if (cursor == DIM) {
        fread(buf, 1, DIM, stdin);
        cursor = 0;
    }
    return buf[cursor];
}

int readInt()
{
    char c;
    for (c = getChar(); c != '-' && !(c >= '0' && c <= '9'); c = getChar())
        cursor++;
    int semn = 1, nr = 0;
    if (c == '-') {
        semn = -1;
        cursor++;
    }
    for (c = getChar(); c >= '0' && c <= '9'; c = getChar()) {
        nr = nr*10 + c-'0';
        cursor++;
    }
    return semn*nr;
}

void citire()
{
	n = readInt();
    for (int i = 1; i <= n; i++) {
        mat[i].x = readInt();
        mat[i].y = readInt();
    }
    m = readInt();
    for (int i = 1; i <= m; i++) {
        drlo[i].x = readInt();
        drlo[i].y = readInt();
        drhi[i].x = readInt();
        drhi[i].y = readInt();
    }
}

bool cmp(punct e, punct f)
{
    if (e.x != f.x) return e.x < f.x;
    return e.y < f.y;
}
struct kdnod
{
	punct inf;
	int cate;
    kdnod *st, *dr;
    kdnod(punct _inf = punct(0, 0), int _cate = 0)
    {
		this->inf = _inf;
		this->cate = _cate;
		this->st = nullptr;
		this->dr = nullptr;
    }
};
kdnod *root;
bool xpcomp(punct e, punct f)
{
    return cmp(e, f);
}
bool ypcomp(punct e, punct f)
{
    if (e.y != f.y) return e.y < f.y;
    return e.x < f.x;
}
kdnod *build(vector<punct> &v, int dir)
{
	if (v.empty()) return nullptr;
    kdnod *t;
    punct crt;
    if (v.size() == 1) {
		t = new kdnod(*v.begin(), v.size());
		return t;
    }
    vector<punct> st, dr;
    if (dir == 0) {
		nth_element(v.begin(), v.begin()+v.size()/2, v.end(), xpcomp);
		crt = v[v.size()/2];
		for (int i = 0; i < v.size(); i++)
			if (i == v.size()/2) continue;
			else if (v[i].x <= crt.x)
				st.push_back(v[i]);
			else
				dr.push_back(v[i]);
	}
	else {
		nth_element(v.begin(), v.begin()+v.size()/2, v.end(), ypcomp);
		crt = v[v.size()/2];
		for (int i = 0; i < v.size(); i++)
			if (i == v.size()/2) continue;
			else if (v[i].y <= crt.y)
				st.push_back(v[i]);
			else
				dr.push_back(v[i]);
	}
    t = new kdnod(crt, v.size());
	t->st = build(st, !dir);
	t->dr = build(dr, !dir);
    return t;
}

inline bool contain(int x0, int x1, int y0, int y1, int px, int py)
{
    return px >= x0 && px <= x1 && py >= y0 && py <= y1;
}

int query(kdnod *nod, int x0, int x1, int y0, int y1, int dir, int xst, int xdr, int yst, int ydr)
{
	if (nod == nullptr) return 0;
    if (xst <= x0 && yst <= y0 && x1 <= xdr && y1 <= ydr)
		return nod->cate;
    if (!contain(x0, x1, y0, y1, xst, yst) && !contain(x0, x1, y0, y1, xst, ydr) &&
		!contain(x0, x1, y0, y1, xdr, yst) && !contain(x0, x1, y0, y1, xdr, ydr) &&
		!contain(xst, xdr, yst, ydr, x0, y0) && !contain(xst, xdr, yst, ydr, x0, y1) &&
		!contain(xst, xdr, yst, ydr, x1, y0) && !contain(xst, xdr, yst, ydr, x1, y1) &&
		!(x0 <= xst && y0 <= yst && xdr <= x1 && ydr <= y1))
		return 0;
    if (dir == 0) {
		int v = contain(xst, xdr, yst, ydr, nod->inf.x, nod->inf.y);
        return v + query(nod->st, x0, nod->inf.x, y0, y1, !dir, xst, xdr, yst, ydr) +
			   query(nod->dr, nod->inf.x+1, x1, y0, y1, !dir, xst, xdr, yst, ydr);
    }
    else {
    	int v = contain(xst, xdr, yst, ydr, nod->inf.x, nod->inf.y);
		return v + query(nod->st, x0, x1, y0, nod->inf.y, !dir, xst, xdr, yst, ydr) +
			   query(nod->dr, x0, x1, nod->inf.y+1, y1, !dir, xst, xdr, yst, ydr);
    }
}

void init()
{
	vector<punct> f;
	for (int i = 1; i <= n; i++)
		f.push_back(mat[i]);
	root = build(f, 0);
}

void solve()
{
	nth_element(mat+1, mat+1, mat+n+1, xpcomp); int x0 = mat[1].x;
    nth_element(mat+1, mat+n, mat+n+1, xpcomp); int x1 = mat[n].x;
    nth_element(mat+1, mat+1, mat+n+1, ypcomp); int y0 = mat[1].y;
    nth_element(mat+1, mat+n, mat+n+1, ypcomp); int y1 = mat[n].y;
    for (int i = 1; i <= m; i++) {
        int rez = query(root, x0, x1, y0, y1, 0, drlo[i].x, drhi[i].x, drlo[i].y, drhi[i].y);
        printf("%d\n", rez);
    }
}

int main()
{
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);

	fread(buf, 1, DIM, stdin);
    citire();
    init();
    solve();

    return 0;
}