Cod sursa(job #1518229)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 5 noiembrie 2015 19:20:14
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <tuple>
using namespace std;

using ograda = tuple<int, int>;
using oaie = tuple<int, int>;
using nume_celula = tuple<int, int>;
using info_celula = tuple<vector<int>, vector<int> >;

struct celula_hash : public unary_function<nume_celula, size_t>{
	size_t operator()(const nume_celula& n)const{
		return (get<0>(n)>>1) ^ (get<1>(n)<<1); } };

bool included(const int w, const int h, const int xdr, const int ydr, const int xp, const int yp){
	return xdr <= xp && ydr <= yp && xp <= xdr+w && yp <= ydr+h; }

int main(){
	ifstream f("ograzi.in");
	ofstream g("ograzi.out");
	int n, m, w, h;
	f >> n >> m >> w >> h;
	unordered_map<nume_celula, info_celula, celula_hash> celule;
	vector<tuple<int, int> > ograzi(n), oi(m);
	for(int i = 0, x, y; i < n; ++i){
		f >> x >> y;
		ograzi[i] = tuple<int, int>(x, y);
		const int x_ = x/w, y_ = y/h;
		for(int dx = 0; dx <= 1; ++dx){
			for(int dy = 0; dy <= 1; ++dy){
				get<0>(celule[tuple<int, int>(x_+dx, y_+dy)]).push_back(i); } } }
	for(int i = 0, x, y; i < m; ++i){
		f >> x >> y;
		oi[i] = tuple<int, int>(x, y);
		get<1>(celule[tuple<int, int>(x/w, y/h)]).push_back(i); }
	int rez = 0;
	for(const auto& c : celule){
		const auto& info = get<1>(c);
		for(const auto ograda : get<0>(info)){
			for(const auto oaie : get<1>(info)){
				//cout << ograda << ' ' << oaie << ' ';
				if(included(w, h, get<0>(ograzi[ograda]), get<1>(ograzi[ograda]),
					get<0>(oi[oaie]), get<1>(oi[oaie]))){
					//cout << '*';
					++rez; }
				//cout << endl;
				} } }
	g << rez;
	return 0; }