UVA 11345 Rectangles(n个矩形重叠覆盖的面积)
题意:
给你n个矩形的左上角和右下角,要你输出那些被所有矩形都覆盖的面积大小.
分析:
本题与POJ 1151 Atlantis基本类似,详细分析可以参考:
http://blog.csdn.net/u013480600/article/details/39322791
下面简单说下本题的主要思想:
获得了n个矩形,那么我们把所有矩形的X和Y坐标取出来,就可以把整个二维平面分成很多个小网格(网格面积不一定相同),任何一个原始矩形都包含了1个或多个小网格. 然后我们只要一次扫描,看看每个小网格被多少个原始矩形覆盖即可. 最终我们求出那些覆盖数==n的小网格的面积和输出即可.
AC代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100+5;
struct Node//矩形
{
int x1,y1,x2,y2;
}nodes[maxn];
int n;//n个矩形
int x[maxn],y[maxn];
int num1,num2;//记录有多少不同x和y坐标
int mp[maxn][maxn];//标记小网格被覆盖多少次
int main()
{
int T; scanf("%d",&T);
for(int kase=1;kase<=T;++kase)
{
num1=num2=0;
memset(mp,0,sizeof(mp));
scanf("%d",&n);
for(int i=0;i<n;++i)
{
scanf("%d%d%d%d",&nodes[i].x1,&nodes[i].y1,&nodes[i].x2,&nodes[i].y2);
x[num1++]=nodes[i].x1;
x[num1++]=nodes[i].x2;
y[num2++]=nodes[i].y1;
y[num2++]=nodes[i].y2;
}
sort(x,x+num1);
sort(y,y+num2);
num1=unique(x,x+num1)-x;
num2=unique(y,y+num2)-y;
for(int i=0;i<n;++i)
{
int L_x=lower_bound(x,x+num1,nodes[i].x1)-x;
int R_x=lower_bound(x,x+num1,nodes[i].x2)-x;
int L_y=lower_bound(y,y+num2,nodes[i].y1)-y;
int R_y=lower_bound(y,y+num2,nodes[i].y2)-y;
for(int j=L_x;j<R_x;++j)
for(int k=L_y;k<R_y;++k)
mp[j][k]++;
}
int ans=0;
for(int i=0;i<num1;++i)
for(int j=0;j<num2;++j)
if(mp[i][j]==n) ans+= (x[i+1]-x[i])*(y[j+1]-y[j]);
printf("Case %d: %d\n",kase,ans);
}
return 0;
}
分享到:
相关推荐
matlab开发-rectangles。快速绘制多个矩形。
研究关于将一个矩形分割为多个矩形的论文,来自路易斯安那州立大学数学系,亦可从作者的个人主页上下载: www.math.lsu.edu/~verrill/research/rectangles.pdf
嵌套矩形js 在Javascript中绘制n个具有不同颜色(数组)的嵌套矩形 例子 document.body.appendChild(addRect(15));
Matthew Eicholtz编写的一个非常有用的函数“ RECTANGLES”通过将多个矩形绘制为单个面片来解决了我的问题。 https://www.mathworks.com/matlabcentral/fileexchange/59243-rectangles 但是,当我想向矩形添加曲率...
Word VBA中通过Rectangles选中页眉、页脚、正文(包含整页内容、整行、字符)
可移动矩形 使用canvas实现可移动的矩形
zoj 1179 Finding Rectangles.md
该函数根据向量 xx 和 yy 设置的网格生成矩形网格。 函数[节点,矩形]=Rectangles_Mesh(xx,yy) 输入xx 和 yy 分别是大小为 (Nx,1) 和 (Ny,1) 的... Rectangles((Nx-1)*(Ny-1),4) 是逆时针方向每个元素的节点连接矩阵。
All_Rectangles:完美的正方形或不相等的矩形,不用担心,java程序可在大Rectangle中查找矩形的数量
HomeworkHelpOnline.net-Python:查找矩形 查找比背景暗的纯色矩形。 查看rect_final.py以获取主要代码。 所有支持功能都在customFunctions.py中。
本文实例主要是在演示框里实现一个移动的矩形实例代码,完整代码如下: #moving rectangle project import pygame from pygame.locals import * pygame.init() screen = pygame.display.set_mode((600,500)) pygame...
安装下载软件包或克隆存储库,然后使用以下命令安装: python setup.py install 或使用pypi: pip install rectpack基本用法将矩形打包到多个箱中非常简单: from rectpack import newPackerrectangles = [( 100 , ...
项目实现启发式二维矩形打包算法### Used for:在凸凹容器中包装尽可能多的矩形基于论文中描述的想法: "A heuristic approach for packing rectangles in convex regions" by Andrea Cassioli, Marco Locatelli" ...
行业教育软件-学习软件-Triangles Rectangles Solver 1.2 英文版.zip
union_of_rectangles 该存储库包含段树的基本实现,以及它在各种与矩形联合相关的应用程序中的使用。 具体来说,是矩形的并集,周长和轮廓。 这些实现的算法是从Preparata和Shamos所著的“计算几何-简介”一书中借用...
二维矩形的层次hp有限元法 采用分层形状函数实现矩形hp FEM,可有效组装质量和刚度矩阵。
层次全局形状函数的排序由几个索引矩阵给出。该代码提供了八个示例,演示了在二维矩形上实现分层hp FEM。
此应用程序将为您提供任何三角形中的所有三角函数未知信息!
for (const [len, width] of rectangles) {for (const [len, width] of rectangles) {
Draw rectangles and filled rectangles