Cod sursa(job #542044)

Utilizator militerMilitaru Gabriel Ovidiu militer Data 25 februarie 2011 18:40:24
Problema Reuniune Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include<algorithm>
#include<fstream>
#include<iostream>
using namespace std;

typedef struct{long long xst,yst,xdr,ydr;} DR;
DR D[4];
long long i,j,n;
long long P,A;
long long Y[20],X[20];
long long st,dr,p;
ifstream fi("reuniune.in");
ofstream fo("reuniune.out");
void citeste(DR & D)
{
	fi>>D.xst>>D.yst>>D.xdr>>D.ydr;
}

int f1(DR d1,DR d2)
//pentru ordonare dupa x
{
	if(d1.xst<=d2.xst)
		return 1;
	return 0;
}

int f2(DR d1,DR d2)
{
	if(d1.yst<=d2.yst)
		return 1;
	return 0;
}

long long maxi(long long a,long long b)
{
	if(a<b)
		return b;
	else
		return a;
}


int main() 
{
	int i;
	for(i=1;i<=3;i++)
	citeste(D[i]);
	sort(D+1,D+4,f1);
	//se proiecteaza vf dreptunghiurilor pe OY
	n=0;
	for(i=1;i<=3;i++) 
	{
		Y[++n]=D[i].yst;
		Y[++n]=D[i].ydr;
	}
	sort(Y+1,Y+n+1);
	for(i=1;i<=n-1;i++)
	{
		//se intersecteaza banda Y[i]- Y[i+1] cu toate dreptunghiurile
		st=dr=-200000000;
		for(j=1;j<=3;j++)
			if(D[j].yst<=Y[i] && D[j].ydr>=Y[i+1])
				if(dr<D[j].xst)
					if(st!=dr)
					{
						A+=(Y[i+1]-Y[i])*(dr-st);//L*l
						P+=(2*(Y[i+1]-Y[i]));
						st=D[j].xst;
						dr=D[j].xdr;
					}
					else
					{
					st=D[j].xst;
					dr=D[j].xdr;
					}
				else
				{
					dr=maxi(dr,D[j].xdr);
				}
			if(st!=dr)
			{	P+=(2*(Y[i+1]-Y[i]));
				A+=(Y[i+1]-Y[i])*(dr-st);
			}
	}
		for(i=1;i<=3;i++) 
	{
		Y[++n]=D[i].yst;
		Y[++n]=D[i].ydr;
	}
	sort(Y+1,Y+n+1);
	for(i=1;i<=3;i++) 
	{
		X[++n]=D[i].xst;
		X[++n]=D[i].xdr;
	}
	sort(D+1,D+4,f2);
	for(i=1;i<=n-1;i++)
	{
		//se intersecteaza banda Y[i]- Y[i+1] cu toate dreptunghiurile
		st=dr=-200000000;
		for(j=1;j<=3;j++)
			if(D[j].xst<=X[i] && D[j].xdr>=X[i+1])
				if(dr<D[j].yst)
					if(st!=dr)
					{
						P+=(2*(X[i+1]-Y[i]));
						st=D[j].yst;
						dr=D[j].ydr;
					}
					else
					{
					st=D[j].yst;
					dr=D[j].ydr;
					}
				else
					dr=maxi(dr,D[j].ydr);
			if(st!=dr)
				P+=(2*(X[i+1]-X[i]));
	}
	fo<<A<<" "<<P;
	fi.close();
	fo.close();
	return 0;
}