codevs 3044_矩形面积求并_离散

2019-11-08 19:59:43

字体：大中小

来源：转载

供稿：网友

题目描述

输入n个矩形，求他们总共占地面积

思路

离散化后算出每一个小矩形的面积，加起来就可以了然后数组范围要注意一下。。。 O(nlogn)

#include <stdio.h>#include <algorithm>using namespace std;struct arr{ double x1,x2,y1,y2;}a[10000];int cam(double x,double y){ return x<y;}double dx[10000],dy[10000],f[10000];int main(){ int n,ll=0; scanf("%d",&n); ll++; int t=0; while (n!=0) { for (int i=0;i<10000;i++) { a[i].x1=a[i].x2=a[i].y1=a[i].y2=dx[i]=dy[i]=f[i]=0; } for (int i=1;i<=n;i++) { scanf("%lf%lf%lf%lf",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2); t++; dx[t]=a[i].x1; dy[t]=a[i].y1; t++; dx[t]=a[i].x2; dy[t]=a[i].y2; } sort(dx+1,dx+t+1,cam); sort(dy+1,dy+t+1,cam); double ans=0; for (int i=1;i<=t-1;i++) { double x1=dx[i],l=0,r=0; for (int j=1;j<=t-1;j++) { double y1=dy[j],x2=dx[i+1],y2=dy[j+1]; if (x2==x1||y1==y2) continue; for (int k=1;k<=n;k++) { if (a[k].x1<=x1&&a[k].y1<=y1&&a[k].x2>x1&&a[k].y2>y1) { ans+=(x2-x1)*(y2-y1); break; } } } } PRintf("%.2lf/n",ans); scanf("%d",&n); }}

上一篇：c语言实现线性表之顺序存储结构

下一篇：eclipse初始化使用