C++(g++ 7.5.0) 解法, 执行用时: 4ms, 内存消耗: 400K, 提交时间: 2022-08-29 10:58:23

#include<bits/stdc++.h>
#define N 10005
using namespace std;
int n,cnt;
struct pp{
	double x,l,r,v;
}f[2*N];
struct xx{
	int p,l,r;
	double bj,sum;
}w[4*N];
double g[N],ans,h[N];
map<double,int>val;
bool cmp(pp p,pp q)
{
	return p.x<q.x;
}
void build(int p,int l,int r)
{
	w[p].l=l;
	w[p].r=r;
	w[p].bj=w[p].sum=0;
	if(l==r)	return ;
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void add(int p,int ll,int rr,int v)
{
	int l=w[p].l;
	int r=w[p].r;
//	cout<<l<<" "<<r<<" "<<ll<<" "<<rr<<endl;
	if(ll<=l&&r<=rr)
	{
		w[p].bj+=v;
		if(l==r)
		{
			if(w[p].bj>0)	w[p].sum=h[r+1]-h[l];
			else 			w[p].sum=0;
			return ;
		}
	}
	int mid=(l+r)/2;
	if(ll<=mid)	add(p*2,ll,rr,v);
	if(mid<rr)	add(p*2+1,ll,rr,v);
	if(w[p].bj>0)	w[p].sum=h[r+1]-h[l];
	else	w[p].sum=w[p*2].sum+w[p*2+1].sum;
}
double ask(int p)
{
	return w[p].sum;
}
int main() 
{
	int s=0;
	while(1)
	{
		s++;
		cin>>n;
		if(n==0)	break;
		cnt=ans=0;
		for(int i=1;i<=n;i++)
		{
			double a,b,c,d;
			cin>>a>>b>>c>>d;
			f[++cnt]={a,b,d,1};
			g[cnt]=b;
			f[++cnt]={c,b,d,-1};
			g[cnt]=d;
		}
		sort(f+1,f+cnt+1,cmp);
		sort(g+1,g+cnt+1);
		int tot=0;
		for(int i=1;i<=cnt;i++)
		if(i==1||g[i]!=g[i-1])
		{
			val[g[i]]=++tot;
			h[tot]=g[i];
		}
		build(1,1,tot-1);
		for(int i=1;i<=cnt;i++)
		{
		//	cout<<ask(1)<<endl;
			ans+=(f[i].x-f[i-1].x)*ask(1);
			add(1,val[f[i].l],val[f[i].r]-1,f[i].v);
		}
		cout<<"Test case #"<<s<<endl;
		printf("Total explored area: %.2lf\n\n",ans);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 344K, 提交时间: 2019-08-29 15:30:50

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
struct rec{double x;int to,e;}a[210],b[210];
int c[110][2],f[210],n,i,j,k,x,y,z,data;
double len,ans,x1,y1,x2,y2;

int cmp(const void *a,const void *b)
{
	return ((rec *)a)->x>((rec *)b)->x?1:-1;
}

int main()
{
	while(cin>>n&&n)
	{
		for(i=1;i<=n;i++) 
		{
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			a[i*2-1].x=x1; a[i*2-1].to=i; a[i*2-1].e=1;
			a[i*2].x=x2; a[i*2].to=i; a[i*2].e=-1;
			b[i*2-1].x=y1; b[i*2-1].to=i; b[i*2-1].e=0;
			b[i*2].x=y2; b[i*2].to=i; b[i*2].e=1;
		}
		qsort(b+1,2*n,sizeof(b[1]),cmp);
		qsort(a+1,2*n,sizeof(a[1]),cmp);
		for(i=1;i<=2*n;i++) c[b[i].to][b[i].e]=i;
		memset(f,0,sizeof(f));
		for(ans=0,i=1;i<2*n;i++)
		{
			j=a[i].to; x=c[j][0]; y=c[j][1]; z=a[i].e;
			for(k=x;k<y;k++) f[k]+=z;
			for(len=0,k=1;k<2*n;k++) if(f[k]) len+=b[k+1].x-b[k].x;
			ans+=len*(a[i+1].x-a[i].x);
		}
        if (data) printf("\n");
		printf("Test case #%d\nTotal explored area: %.2f\n",++data,ans);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 476K, 提交时间: 2020-04-23 20:00:25

#include<bits/stdc++.h>
using namespace std;
const int N=110;
struct node {
	double x,y1,y2;
	int k;
	bool operator <(const node y) const {
		return x<y.x;
	}
} a[2*N];
double raw[2*N];
map<double,int>val;
int n,num=0;
void atl() {
	double y1,y2;
	for(int i=1; i<=n; i++) {
		cin>>a[2*i-1].x>>y1>>a[2*i].x>>y2;
		raw[2*i-1]=a[2*i].y1=a[2*i-1].y1=y1;
		raw[2*i]=a[2*i-1].y2=a[2*i].y2=y2,a[2*i-1].k=1;
		a[2*i].k=-1;
	}
	n<<=1;
	sort(a+1,a+n+1);
	sort(raw+1,raw+n+1);
	//------离散化数据
	int m=unique(raw+1,raw+n+1)-(raw+1);
	for(int i=1; i<=m; i++)
		val[raw[i]]=i;
	double ans=0,len=0;
	int c[2*N]= {};
	for(int i=1;i<n;i++){
		int y1=val[a[i].y1],y2=val[a[i].y2];
		for(int j=y1;j<y2;j++)c[j]+=a[i].k;
		len=0;
		for(int j=1;j<m;j++)
		if(c[j])len+=raw[j+1]-raw[j];
		ans+=(a[i+1].x-a[i].x)*len;
	}
	if(num)cout<<endl;
	cout<<"Test case #"<<(++num)<<endl;
	cout<<"Total explored area: "<<fixed<<setprecision(2)<<ans<<endl;
}
int main() {
	while(cin>>n&&n)atl();
	return 0;
}