codevs 3044 직사각형 면적 구 합

05 년 의 그 논문 의 문제 때문에 나 는 찾 을 수 없다.
그리고 이 문 제 를 대체 하여 나의 산법 의 정확성 을 검증 하 였 다.
우선 이 문제 의 선분 트 리 가 가장 좋 으 니 말 할 필요 가 없다.
그리고 논문 에 구덩이 아버지 문제 가 있 는데 사각형 을 색깔 로 염색 한 다음 에 각 색깔 의 면적 을 구한다.
이 럴 때 선분 수 는 n ^ 2 * logn 의 복잡 도 를 가 져 야 합 니 다.
아래 의 이런 방법 은 여전히 n ^ 2 (그러나 나 는 그 문 제 를 찾 지 못 했다)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct seg{
	double l,r,x;
	int id,a,b;
	bool operator < (const seg &rhs)const{
		return x<rhs.x;
	}
}s[205];
bool ex[105];
int pa[205];
double hash[205];
int find(int x){
	return pa[x]==x?x:pa[x]=find(pa[x]);
}
void merge(int u,int v){
	u=find(u);v=find(v);
	if(u!=v){
		if(u>v)swap(u,v);
		pa[u]=v;
	}
}
double addseg(seg s){
	int last=s.a;
	double ans=0;
	for(int u=s.a;u<=s.b;){
		ans+=hash[u]-hash[last];
		merge(u,last);
		last=find(u);
		u=last+1;
	}
	return ans;
}
int n;
double work(){
	double ans=0;
	for(int i=1;i<=2*n;i++)pa[i]=i;
	for(int i=1;i<=2*n;i++)
	if(ex[s[i].id])
	ans+=addseg(s[i]);
	return ans;
}
double solve(){
	double ans=0;
	int j;
	for(int i=1;i<=2*n;i=j){
		j=i;
		while(j<=2*n&&s[i].x==s[j].x)
		ex[s[j++].id]^=1;
		ans+=work()*(s[j].x-s[i].x);
	}
	return ans;
}
void init(){
	double x1,x2,y1,y2;
	for(int i=1;i<=n;i++){
		scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
		s[2*i]=(seg){y1,y2,x1,i,0,0};
		s[2*i-1]=(seg){y1,y2,x2,i,0,0};
		hash[2*i]=y1;hash[2*i-1]=y2;
	}
	sort(hash+1,hash+2*n+1);sort(s+1,s+1+2*n);
	for(int i=1;i<=2*n;i++)
	s[i].a=lower_bound(hash+1,hash+1+2*n,s[i].l)-hash,
	s[i].b=lower_bound(hash+1,hash+1+2*n,s[i].r)-hash;
}
int main(){
	//freopen("a.in","r",stdin);
	while(scanf("%d",&n)&&n){
		init();
		printf("%.2lf
",solve());
	}
	return 0;
}