Cod sursa(job #97010)

Utilizator mastermageSchneider Stefan mastermage Data 4 noiembrie 2007 17:37:20
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

#define maxN 2600

struct rec{int x1,y1,x2,y2,c;bool operator<(rec const&r)const{return c<r.c;}};
struct lin{int p,s,e;lin(){}lin(int pp,int sp,int ep){p=pp,s=sp,e=ep;}};

template<class t>void del(t*v,int&n,int p){for(int i=p+1;i<n;i++)v[i-1]=v[i];n--;}
template<int rec::*p> bool pred(rec const&l,rec const&r){return l.*p<r.*p;};
template<int rec::*p> int bs(rec*v,int n,int x){
	int s=0,e=n-1,m;
	while(s<e){
		m=s+e>>1;
		if(v[m].*p<x)s=m+1;else e=m;
	}
	return s;
}


int n,kle,kri,kup,kdw;
long long res;
rec v[maxN];
lin le[maxN],ri[maxN],up[maxN],dw[maxN];

void inputFunc(){FILE*fi=fopen("teren.in","r");fscanf(fi,"%d",&n);for(int i=0;i<n;i++){fscanf(fi,"%d %d %d %d %d",&v[i].x1,&v[i].y1,&v[i].x2,&v[i].y2,&v[i].c);}fclose(fi);}
void outputFunc(){FILE*fi=fopen("teren.out","w");fprintf(fi,"%lld",res);fclose(fi);}



void cul(rec*v,int n){
	kle=kri=kup=kdw=0;
	sort(v,v+n,pred<&rec::x1>);
	for(int i=0;i<n;i++){				//cicleaza prin toate patratele
		int cur=v[i].x2,pa=bs<&rec::x1>(v,n,cur),ks=kri;
		ri[kri++]=lin(cur,v[i].y1,v[i].y2);
		for(int j=pa;v[j].x1==cur;j++){  //totate patratle adicente
			int a=v[j].y1,b=v[j].y2;
			for(int q=ks;q<kri;q++){		//cicleaza prin toate linile create
				int la=ri[q].s,lb=ri[q].e;
				if(a<=la && b>la){
					if(b>=lb)del(ri,kri,q);else ri[q].s=b;
					break;
				}
				if(a>la && a<lb){
					ri[q].e=a;
					if(b<lb)ri[kri++]=lin(cur,b,lb);
					break;
				}
			}
		}
	}
	
	sort(v,v+n,pred<&rec::x2>);
	for(int i=0;i<n;i++){				//cicleaza prin toate patratele
		int cur=v[i].x1,pa=bs<&rec::x2>(v,n,cur),ks=kle;
		le[kle++]=lin(cur,v[i].y1,v[i].y2);
		for(int j=pa;v[j].x2==cur;j++){  //totate patratle adicente
			int a=v[j].y1,b=v[j].y2;
			for(int q=ks;q<kle;q++){		//cicleaza prin toate linile create
				int la=le[q].s,lb=le[q].e;
				if(a<=la && b>la){
					if(b>=lb)del(le,kle,q);else le[q].s=b;
					break;
				}
				if(a>la && a<lb){
					le[q].e=a;
					if(b<lb)le[kle++]=lin(cur,b,lb);
					break;
				}
			}
		}
	}
	
}

int main(){
	inputFunc(); sort(v,v+n);
	int lst=0;
	for(int i=1;i<=n;i++)if(v[lst].c!=v[i].c){
		cul(v+lst,i-lst);		
 	}
	outputFunc();
	return 0;
}