Cod sursa(job #865496)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 26 ianuarie 2013 16:26:04
Problema Sortare prin comparare Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.19 kb

#include <cstdio>
#include <cstdlib>
#include <ctime>

const int MAX_N(101);
const int MAX_SIZE(500);
const int MAX_VALUE(8001);

int n, m, p, result, points;

bool matrix [MAX_SIZE] [MAX_SIZE];

struct rectangle
{
	int x1, y1, x2, y2;
} rectangles [MAX_N];

struct coord
{
	int i;
	int j;
} queue [MAX_SIZE * MAX_SIZE * 2];

int x [MAX_SIZE], y [MAX_SIZE], normx [MAX_VALUE], normy [MAX_VALUE];

inline void swap (int &a, int &b)
{
	int temp(a);
	a = b;
	b = temp;
}

inline void read (void)
{
	points = 2;
	std::freopen("colaj.in","r",stdin);
	std::scanf("%d\n%d %d",&n,&m,&p);
	x[1] = m;
	y[1] = p;
	for (int index(1) ; index <= n ; ++index)
	{
		std::scanf("%d %d %d %d",&rectangles[index].x1,&rectangles[index].y1,&rectangles[index].x2,&rectangles[index].y2);
		x[points] = rectangles[index].x1;
		x[points + 1] = rectangles[index].x2;
		y[points] = rectangles[index].y1;
		y[points + 1] = rectangles[index].y2;
		points += 2;
	}
	std::fclose(stdin);
}

inline void print (void)
{
	std::freopen("colaj.out","w",stdout);
	std::printf("%d\n",result);
	std::fclose(stdout);
}

void quicksort (int v [ ], int left, int right)
{
	int pivot(v[left + std::rand() % (right - left + 1)]);
	int i(left), j(right);
	while (i < j)
	{
		while (v[i] < pivot)
			++i;
		while (v[j] > pivot)
			--j;
		if (i <= j)
		{
			swap(v[i],v[j]);
			++i;
			--j;
		}
	}
	if (left < j)
		quicksort(v,left,j);
	if (right > i)
		quicksort(v,i,right);
}

inline void normalize (void)
{
	quicksort(x,0,points - 1);
	quicksort(y,0,points - 1);
	int index, point;
	for (index = 0, point = 1 ; index < points ; ++index)
		if (!normx[x[index]])
		{
			normx[x[index]] = point;
			point += 2;
		}
	for (index = 0,  point = 1 ; index < points ; ++index)
		if (!normy[y[index]])
		{
			normy[y[index]] = point;
			point += 2;
		}
	for (index = 1 ; index <= n ; ++index)
	{
		rectangles[index].x1 = normx[rectangles[index].x1];
		rectangles[index].x2 = normx[rectangles[index].x2];
		rectangles[index].y1 = normy[rectangles[index].y1];
		rectangles[index].y2 = normy[rectangles[index].y2];
	}
	m = normx[m];
	p = normy[p];
}

inline void draw (void)
{
	int a, b, c, d, i, j;
	for (i = 0 ; i <= m + 1 ; ++i)
		matrix[0][i] = matrix[p + 1][i] = true;
	for (i = 0 ; i <= p + 1 ; ++i)
		matrix[i][0] = matrix[i][m + 1] = true;
	for (int index(1) ; index <= n ; ++index)
	{
		a = rectangles[index].x1;
		b = rectangles[index].y1;
		c = rectangles[index].x2;
		d = rectangles[index].y2;
		for (i = b ; i <= d ; ++i)
			for (j = a ; j <= c ; ++j)
				matrix[i][j] = true;
	}
}

inline void fill (int i, int j)
{
	static const int X [ ] = {-1,0,1,0};
	static const int Y [ ] = {0,1,0,-1};
	struct coord *push(queue + 1), *pop(queue);
	queue->i = i;
	queue->j = j;
	int k;
	matrix[i][j] = true;
	do
	{
		i = pop->i;
		j = pop->j;
		++pop;
		for (k = 0 ; k < 4 ; ++k)
			if (!matrix[i + X[k]][j + Y[k]])
			{
				push->i = i + X[k];
				push->j = j + Y[k];
				matrix[push->i][push->j] = true;
				++push;
			}
	}
	while (pop < push);
}

inline void fill (void)
{
	int i, j;
	for (i = 1 ; i <= p ; ++i)
		for (j = 1 ; j <= m ; ++j)
			if (!matrix[i][j])
			{
				fill(i,j);
				++result;
			}
}

int main (void)
{
	std::srand(std::time(0));
	read();
	normalize();
	draw();
	fill();
	print();
	return 0;
}