TIOJ 1045 A.細菌培養 [discretization]

poao899    1520K    515MS    G++     1.37K     2009-12-08 13:58:43                                               .

離散化暴力。

//如果用二維線段樹複雜度會多lg^2 n耶XD也沒有比較好coˊˋ

你可以假設這個數字小於8*10^18 看成8*10^8是哪招orz


//***************************

//1045

#include<stdio.h>
#include<algorithm>
struct seq{
	int ar[440],cnt;
	int put(int v){
		ar[cnt++]=v;
	}
	void show(){
		for(int i=0;i<cnt;i++)
			printf("%d\n",ar[i]);
		puts("");
	}
	int bs(int val){
		int l=0,r=cnt-1,mid;
		while(l!=r){
			mid=(l+r)/2;
			if(ar[mid]<val)l=mid+1;
			else r=mid;
		}
		return l;
	}
}w,h;
long long val[440][440],n;
int wi[440][2],he[440][2];
main(){
	while(scanf("%d",&n),n){
		//Initialize
		for(int i=0;i<440;i++)
			for(int j=0;j<440;j++)
				val[i][j]=1;
		w.cnt = h.cnt = 0;
		//Input
		w.put(0);w.put(10000);
		h.put(0);h.put(10000);
		for(int i=0;i<n;i++){
			scanf("%d%d%d%d",&wi[i][0],&he[i][0],&wi[i][1],&he[i][1]);
			w.put(wi[i][0]);
			w.put(wi[i][1]);
			h.put(he[i][0]);
			h.put(he[i][1]);
		}
		std::sort(w.ar,w.ar+w.cnt);
		std::sort(h.ar,h.ar+h.cnt);
		for(int i=0;i<n;i++){
			int wl=w.bs(wi[i][0]),wr=w.bs(wi[i][1]),hl=h.bs(he[i][0]),hr=h.bs(he[i][1]);
			for(int j=wl;j<wr;j++)
				for(int k=hl;k<hr;k++)
					val[j][k]*=2;
		}
		//w.show();h.show();
		long long total=0;
		for(int i=0;i<w.cnt-1;i++)
			for(int j=0;j<h.cnt-1;j++)
				total+=(long long)(w.ar[i+1]-w.ar[i])*(h.ar[j+1]-h.ar[j])*val[i][j];
		printf("%I64d\n",total);
	}
}