首页 > 代码库 > 矩形面积求并（codevs 3044）
矩形面积求并（codevs 3044）
题目描述 Description
输入n个矩形，求他们总共占地面积（也就是求一下面积的并）
输入描述 Input Description
可能有多组数据，读到n=0为止(不超过15组)
每组数据第一行一个数n，表示矩形个数(n<=100)
接下来n行每行4个实数x1,y1,x2,y1(0 <= x1 < x2 <= 100000;0 <= y1 < y2 <= 100000)，表示矩形的左下角坐标和右上角坐标
输出描述 Output Description
每组数据输出一行表示答案
样例输入 Sample Input
210 10 20 2015 15 25 25.50
样例输出 Sample Output
180.00
数据范围及提示 Data Size & Hint
无
/* 将所有正方形沿线切割成一个个小正方形，然后离散化。 */ #include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#define M 210using namespace std;double x[M],y[M],s[M][4];int xy[M][M];int n,cas=0;double sum;int main(){ while(cin>>n) { if(n==0)break; cas++; sum=0.0; memset(xy,0,sizeof(xy)); for(int i=1;i<=n;i++) { cin>>s[i][0]>>s[i][1]>>s[i][2]>>s[i][3]; x[i*2-2]=s[i][0]; y[i*2-2]=s[i][1]; x[i*2-1]=s[i][2]; y[i*2-1]=s[i][3]; } sort(x,x+2*n); sort(y,y+2*n); for(int k=1;k<=n;k++) { int x1,x2,y1,y2; for(x1=0;x1<2*n;x1++) if(x[x1]==s[k][0])break; for(x2=0;x2<2*n;x2++) if(x[x2]==s[k][2])break; for(y1=0;y1<2*n;y1++) if(y[y1]==s[k][1])break; for(y2=0;y2<2*n;y2++) if(y[y2]==s[k][3])break; for(int i=x1;i<x2;i++) for(int j=y1;j<y2;j++) xy[i][j]=1; } for(int i=0;i<2*n;i++) for(int j=0;j<2*n;j++) sum+=xy[i][j]*(x[i+1]-x[i])*(y[j+1]-y[j]); printf("%.2f\n",sum); } return 0;}
矩形面积求并（codevs 3044）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。