首页 > 代码库 > codevs 3044 矩形面积求并

codevs 3044 矩形面积求并

2024-09-22 04:24:50   216人阅读

3044 矩形面积求并

时间限制: 1 s  空间限制: 256000 KB  题目等级 : 钻石 Diamond

题目描述 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
2
10 10 20 20
15 15 25 25.5
0

样例输出 Sample Output

180.00
思路：转化为二维线段覆盖问题。
喜闻乐见的Code
#include<cstdio>#include<algorithm>using namespace std;#define maxn 103typedef double d;d x1[maxn],y1[maxn],x2[maxn],y2[maxn];d x[maxn<<1],y[maxn<<1];int main() {	int n;	while(scanf("%d",&n)==1&&n!=0) {		int cnt=0;d sum=0;		for(int i=1;i<=n;i++) {				scanf("%lf%lf%lf%lf",&x1[i],&y1[i],&x2[i],&y2[i]);			x[++cnt]=x1[i];y[cnt]=y1[i];			x[++cnt]=x2[i];y[cnt]=y2[i];		}		sort(x+1,x+cnt+1);sort(y+1,y+cnt+1);		for(int i=2;i<=cnt;i++)			for(int j=2;j<=cnt;j++) {				d p1=x[i-1],q1=y[j-1],p2=x[i],q2=y[j];				for(int k=1;k<=n;k++)					if(p1>=x1[k]&&q1>=y1[k]&&p2<=x2[k]&&q2<=y2[k]) {						sum+=(p2-p1)*(q2-q1);						break;					}			}		printf("%.2lf\n",sum);	}	return 0;}

　　

codevs 3044 矩形面积求并


联系
我们