1151.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"stdio.h"
#include"vector"
#include <algorithm>
using namespace std;
struct rect
{double xt,yt,xb,yb;
};
struct point
{double x,y;};

double max(double a,double b)
{if(a>b)return a;
	else return b;
}
double min(double a,double b)
{if(a>b)return b;
	        else return a;
}

/*
rect find(rect &a,rect &b)
{rect u;
u.xt=max(a.xt,b.xt);
u.xb=min(a.xb,b.xb);
u.yt=max(a.yt,b.yt);
u.yb=min(a.yb,b.yb);
return u;
}
*/



inline double mj(rect &a)
{return (a.xb-a.xt)*(a.yb-a.yt);}

rect r[100];
vector<double> x,y;


double s;
int n;
/*
inline int isfind(rect &a)
{return a.xt<a.xb&&a.yt<a.yb;}

void go(rect &a,int c,int key)
{rect b;
for(;c<n;c++)if(isfind(b=find(a,r[c])))
{s=s+mj(b)*key;go(b,c+1,key*-1);}	
}*/

inline int in_rect(rect &a,rect &b)
{return a.xt>=b.xt&&a.yt>=b.yt&&a.yb<=b.yb&&a.xb<=b.xb;}

int compare(double a,double b)
{return a<b;}


int main()
{double a,b,c,d;int i,j,c_n=0,ii,jj,k;rect rt;


while(1)
{cin>>n;if(n==0)break;
c_n++;
x.resize(2*n);y.resize(2*n);
for(i=0;i<n;i++)
{cin>>a>>b>>c>>d;
x[2*i]=a;x[2*i+1]=c;
y[2*i]=b;y[2*i+1]=d;
r[i].xt=min(a,c);
r[i].xb=max(a,c);
r[i].yt=min(b,d);
r[i].yb=max(b,d);

}
sort(x.begin(),x.end(),compare);
sort(y.begin(),y.end(),compare);
s=0;

for(i=1;i<2*n;i++)
{ii=i-1;
while(x[i]==x[ii]&&i<2*n)i++;
if(i>=2*n)break;
for(j=1;j<2*n;j++)
	{jj=j-1;
	while(y[j]==y[jj]&&j<2*n)j++;
	if(j>=2*n)break;
	rt.xt=x[ii];rt.xb=x[i];
	rt.yt=y[jj];rt.yb=y[j];
	for(k=0;k<n;k++)
	if(in_rect(rt,r[k]))break;
	
	if(k<n)s+=mj(rt);
	}
}


printf("Test case #%d\nTotal explored area: %.2f\n\n",c_n,s);

}
return 0;
}