Cod sursa(job #503869)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 25 noiembrie 2010 15:34:47
Problema Reuniune Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define D 10
#define INF 1000000002

struct { int x1, x2, y1, y2; } V[3];

int X[D], Y[D], NX, NY;
int M[D][D];
long long P, A;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void elim_dubl (int A[], int &N)
{
	for (int i = 1; i < 8; ++i)
		if (A[i] != A[i-1])
			A[++N] = A[i];
}

void fill (int x, int y, int d)
{
	if ( !(x >= 0 && x <= NX && y >= 0 && y <= NY) || M[x][y] == -1 )
		return; 
	if ( M[x][y] > 0 )
		{
			if (d & 1)
				P += (long long)(Y[y+1] - Y[y]);
			else
				P += (long long)(X[x+1] - X[x]);
			return;
		}
	
	for (int d = 0; d < 4; ++d)
	{
		M[x][y] = -1;
		fill (x + dx[d], y + dy[d], d);	
	}
}

void parc ()
{
	int i, j;
	for (i = 0; i <= NX - 2; ++i)
		for (j = 0; j <= NY - 2; ++j)
			if ( M[i][j] > 0 )
			{			
				A += (X[i+1] - X[i])*(long long)(Y[j+1] - Y[j]);
				M[i][j] = -2;
			}
}

int main ()
{
	int i, j, k;
	
	freopen ("reuniune.in", "r", stdin);
	freopen ("reuniune.out", "w", stdout);
	
	for (i = 0; i < 3; ++i)
	{
		scanf ("%d%d%d%d", &V[i].x1, &V[i].y1, &V[i].x2, &V[i].y2);
		X[i+i] = V[i].x1, X[i+i+1] = V[i].x2;
		Y[i+i] = V[i].y1, Y[i+i+1] = V[i].y2;
	}
	
	X[6] = -INF, X[7] = INF;
	Y[6] = -INF, Y[7] = INF;
	
	sort (X, X + 7);
	sort (Y, Y + 7);
	
	elim_dubl (X, NX);
	elim_dubl (Y, NY);
	
	for (i = 1; i <= NX-2; ++i)
		for (j = 1; j <= NY-2; ++j)
			for (k = 0; k < 3; ++k)
				if (X[i] >= V[k].x1 && X[i+1] <= V[k].x2 && Y[j] >= V[k].y1 && Y[j+1] <= V[k].y2)
					M[i][j] ++;
	
	fill (0, 0, 0);
	parc ();
	
	printf ("%lld ", A);
	printf ("%lld", P);
	
	return 0;
}