首页 > 其他分享 >扫描线的应用1

扫描线的应用1

时间:2024-03-30 15:04:27浏览次数:26  
标签:矩形 扫描线 int 应用 100 include 我们

概述

顾名思义,扫描线通常是在二维空间内,模拟一条线上下扫描,以此达到解决求二维空间的矩形面积或点数问题。

实现方法

通常采用排序,离散化等操作。排序是为了扫描的不重不漏,而离散化是由于我们模拟的扫描线会一段段扫描,可以去掉重复的信息。

 矩形面积

1151 -- Atlantis

给定平面直角坐标系中的n个矩形,求他们的面积并,即这些矩形的并集在平面中覆盖的总面积

下图为网上搜索得

如果我们一个个算出给出的矩形面积,再减去重叠的面积,十分复杂,但是如果我们将其分块处理,将给出的并集分割,保留左右边界的信息。

仔细思考,矩形的宽度我们很容易可以得到,而长度由于分割的原因要额外处理。

网上搜索得,私聊可删

长度求法:矩形1的长为(20-15)+(15-10),

矩形2的长为(20-15)+(15-10)+(25.5-20),

矩形3的长为(25.5-20)+(20-15)。

由上面总结可知,当我们模拟线在矩形左边的那条边时,长度等于左边的y值减去右边的y值(注意是指我们分割之后的矩形而不是题目给我们的矩形)。

据此我们可以先对x和y分别排序那么问题来了,我们如何得到分割后矩形所谓左边的值和右边的y值呢

我们仔细观察一下矩形1到矩形3长度式子的变化,发现当扫描线进入题目给出的矩形左边时,就有在这条边内所有yi的相减式子(yi是排序后所得)给加上,而当扫描线进入题目给我矩形右边时,就会把这条边所有yi的相减式子给减去。

分析到这,我们就会很兴奋的发现马上就能一睹这个题目的真容。既然我们要根据扫描线进入题目矩形左右不同的边进行相加减,那么我们在输入时就对左右两条边进行编号,左边为1右边为-1(为什么要这样编,如果不明白可以再看看上面的矩形长度分析或者看代码自己运行一遍!)

还有一个关于y坐标的问题,我们如何得到上面所说的这条边内排序后的yi?这个问题很基础,就是离散化相关的知识,我们可以定义一个数组,在输入时要先在矩形结构体里面定义这个矩形编号的属性,然后就可以在对y排序后从头遍历这个y数组,以矩形编号和左右边为坐标,存储遍历到多少次的次数(i);(说起来有点抽象,可以看代码来理解。)

下面我们给出代码

​
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
struct rec{double x;int to,e;}a[210],b[210];
int c[110][2],f[210],n,i,j,k,x,y,z,data;
double len,ans,x1,y1,x2,y2;

int cmp(const void *a,const void *b)
{
	return ((rec *)a)->x>((rec *)b)->x?1:-1;
}

int main()
{
	while(cin>>n&&n)
	{
		for(i=1;i<=n;i++) 
		{
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			a[i*2-1].x=x1; a[i*2-1].to=i; a[i*2-1].e=1;
			a[i*2].x=x2; a[i*2].to=i; a[i*2].e=-1;//注意a数组才要对左右边分别编号1和-1,
//因为我们是通过对x的扫描得到分割后的长度。
			b[i*2-1].x=y1; b[i*2-1].to=i; b[i*2-1].e=0;
			b[i*2].x=y2; b[i*2].to=i; b[i*2].e=1;
		}
		qsort(b+1,2*n,sizeof(b[1]),cmp);
		qsort(a+1,2*n,sizeof(a[1]),cmp);
		for(i=1;i<=2*n;i++) c[b[i].to][b[i].e]=i;//离散化之后的坐标
		memset(f,0,sizeof(f));
		for(ans=0,i=1;i<2*n;i++)
		{
			j=a[i].to;//矩形的编号
             x=c[j][0]; y=c[j][1];//矩形这条边内yi离散化之后的值!
             z=a[i].e;
			for(k=x;k<y;k++) f[k]+=z;//这里是关键要认真思考
			for(len=0,k=1;k<2*n;k++) if(f[k]) len+=b[k+1].x-b[k].x;
			ans+=len*(a[i+1].x-a[i].x);
		}
		printf("Test case #%d\nTotal explored area: %.2f\n\n",++data,ans);
	}
	return 0;
}

​

当然这个题目有优化的空间,每次对f数组加z然后又要根据f的值来得到长度,如果我们能维护一段序列,每次扫描到一条边时,对某些值修改,而修改的方法可以类似二分,这样我们的效率就可以大大提升,感兴趣的可以去了解线段树!!!

算法没有最好,只有更优!!!

最大子矩阵

给定一个m*n的矩阵,其中一些格子是空地,标记为F,其他是障碍R。找出一个全部为空地由F组成的面积最大的子矩阵,输出其面积乘以3的结果

输入格式:样例数T,m,n;以下m行n列的字符(F或R)

分析:

当然我们很容易可以想到暴力算法:枚举左上角的坐标和长宽,判断是不是空地,维护一个ans的最大值;时间复杂度为mn的三次方;

这就提示我们要更优的算法,如何更优呢,在我看来能充分利用信息是算法提高效率的一个途径之一。

那么有什么方法是可以充分利用信息的呢?我们很自然可以想到递推!!!

那么怎么递推呢?这就要我们根据题目的特点来思考!

首先有障碍!!!显然如果要递推,这个障碍就是递推的一个转移条件!

其次是矩形!!!矩形方方正正的,联系我们的扫描线,就像这根线移动来移动去!

那么我们大胆假设一个数组,存储着以这个坐标(i,j)为底,能最多向上延长的长度,(up[i][j])

而left[i][j]就是这根扫描线最大能向左移动的距离,right[i][j]同理。

那么这样的话我们就能构造出一个以(i,j)为底边最优的子矩阵

自此,我们就从每一行开始遍历,更新我们的up,left,right!

下面上代码

​
int main() {
	int m, n;
	int map[100][100],up[100][100],right[100][100],left[100][100];
	cin >> m >> n;
	for(int i=0;i<m;i++)
		for (int j = 0; j < n; j++) {
			char ch = getchar();
			while (ch != 'F' && ch != 'R')ch = getchar();
			map[i][j] = ch == 'F' ? 0 : 1;
		}
	int ans = 0;
	for (int i = 0; i < m; i++) {
		int ol = -1, ro = n;
		for (int j = 0; j < n; j++) {//注意遍历顺序
			if (map[i][j] == 1) { up[i][j] = left[i][j] = 0; ol = j;//最新出现的障碍坐标 }
			else {
				up[i][j] = i == 0 ? 0 : up[i - 1][j] + 1;//转移方程
				left[i][j] = i == 0 ? ol + 1 : max( left[i - 1][j],ol + 1 );
			}
		}
		for (int j = n - 1; j >= 0; j--) {//注意遍历顺序
			if (map[i][j]) {  right[i][j] = n; ro = j;  }
			else {
				right[i][j] = i == 0 ? ro - 1 : min(right[i - 1][j], ro - 1);
				ans = max(ans, up[i][j] * (right[i][j] - left[i][j]));
			}
		}
	}
}

​

这样我们就把这道题目解决了

贩卖土地

Selling Land - UVA 12265 - Virtual Judge (vjudge.net)

输入一个n*m的矩阵,与上题一样,有些是空地,有些是障碍,对于每一个空地,求出以它为右下角的空矩阵的最大周长,然后统计这个周长出现的次数。

当然可以用上面讲的那个方法,只要注意是以(i,j)为右下角就行!!!

这里我们可以用单调栈的方法!

什么是单调栈?简单来说还是对信息的充分使用,把不必要的信息去掉,把可能有用的信息留下来!(留下来!)

分析:我们同样用一个数组height[i][j]来保留(i,j)空地的高度,为了得到以(i,j ) 为右下角的最优矩阵,我们要的就是最优左上角!

首先,height这个数组是可以直接转移的,这里我们不多描述

然后,重要的是如何得到这个最优左上角,由于是矩形,显然这个左上角与右下角的高度差是不能大于height的,这就说明可能的选择里面是有这个条件限制的!

下面这个图片白色代表空地,黑色代表着障碍;

假设右下角在第三列(下面图片里面数字2和数字3中间的那一列)可能的最优矩阵就是分别与2和1所在的那一列配对,当右下角到了第四列(数字3那一列)只能与数字3配对

抽象一下,假设右下角为(c0,h0)左上角为(c,h),那么周长就是(c0-c+h0-h+1)*2,上面的height数组以及高度差的限制!!!提示我们可以把h0-h换成h(h意义是高度差)也就是说我们只要维护一个数组保留着可能的最大的h-c(h是高度差!!!)

这样我们每扫描到一个空地,先判断数组最上面的height是不是符合要求,然后如果h-c大于最上面的h0-c0我们就让这个可能最优入栈!通过这个操作栈顶就是最优的解~~~~

如果扫描到障碍就清空栈

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=1010;
int n,m,top,T;
char s[N][N];
int hei[N],ans[N<<1];

struct Rect{
    int c,h;
    Rect (int c=0,int h=0):c(c),h(h){}
}sta[N];

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; ++i) scanf("%s",s[i]);
        memset(hei,0,sizeof(hei));
        memset(ans,0,sizeof(ans));
        for(int i=0, j; i<n; ++i){
            top=-1; // 清空栈  
            for(j=0; j<m; ++j){
                if(s[i][j]=='#'){
                    top=-1; // 若是沼泽,清空栈  
                    hei[j] = 0;
                }else{
                    hei[j]++;
                    Rect r(j,hei[j]);
                    if(top<0) sta[++top] = r;
                    else{
                        // 弹出太高的  
                        while(top>=0 && sta[top].h>=r.h) r.c=sta[top--].c;
                        // 如果加进去可能成为最优解,就加进去  
                        if(top<0 || sta[top].h-sta[top].c<r.h-r.c) sta[++top]=r;
                    }
                    ans[ sta[top].h+j-sta[top].c+1 ] ++;
                }
            }
        }
        for(int i=1; i<=m+n; ++i){
            if(ans[i]) printf("%d x %d\n",ans[i],i*2);
        }
    }
    return 0;
}

此代码搜索得,私聊可删

自此我们的扫描线算法就算了解了一点,可以试着用单调栈算法解决一下最大子矩阵的题目!

标签:矩形,扫描线,int,应用,100,include,我们
From: https://blog.csdn.net/miaoaikun/article/details/137076713

相关文章

  • 洛谷题单指南-图的基本应用-P1127 词链
    原题链接:https://www.luogu.com.cn/problem/P1127题意解读:按字典序排列单词,使得相邻单词的首位字母一样。解题思路:由于单词之间可以相邻的条件是前一个单词的末尾字母和后一个单词的开头字母一样,因此可以遍历每一个单词,再找到每一个可以接在其后面的单词,建立一个邻接表,然后从......
  • Spring Boot框架中的JDK动态代理实践及其应用场景
    引言在Java编程中,JDK动态代理是一种强大的设计模式,它允许我们在运行时动态地创建并实现代理类,从而对目标对象的行为进行增强或控制。这种机制主要由Java标准库java.lang.reflect.Proxy类和java.lang.reflect.InvocationHandler接口提供支持。在诸如SpringBoot这样的企业级开......
  • HOW - 图形格式SVG及其应用
    目录一、介绍:scalablevectorgraphic二、基本使用三、SVG字体:自定义图标或者符号四、SVGSprite:自定义图标五、动态FetchCDNSVG图标六、SVG压缩七、SvgvsCanvas一、介绍:scalablevectorgraphicSVG是可缩放矢量图形(ScalableVectorGraphics)的缩写......
  • Kubernetes之存储原理和应用——持久卷(PV)
    一、概念解析1.PV与PVC为了能够屏蔽底层存储实现的细节,让用户方便使用及管理员方便管理,Kubemetes从1.0版本开始引入了PersistentVolume(PV)与PersistentVolumeClaim(PVC)资源对象来实现存储管理子系统。PV是对存储资源的抽象,将存储定义为一种容器应用可以使......
  • SpringCloud下的微服务应用技术(结尾篇)
    六.Feign远程调用6.1替代RestTemplateRestTemplate调用问题:代码可读性差,参数复杂且URL难维护。Feign是一个声明式的HTTP客户端,官方地址:GitHub-OpenFeign/feign:Feignmakeswritingjavahttpclientseasier它可以解决上述提到的问题。STEP1:首先,在orderservice中引......
  • 【编码器应用】第一节-编码器从从原理到应用详解
    概述:本文内容为常用电机编码器概览,将为您重点介绍编码器大致分类,以及增量编码器与西门子设备的配置连接方式。编码器简介编码器是利用LED光源发出的透射光对码盘进行光电扫描,光电元件接收编码器轴旋转时产生的明暗交替变化,将电机轴的转速和位置转化为电信号反馈给PLC或者驱......
  • playbook的介绍、应用与实施
    playbook的介绍、应用与实施文章目录playbook的介绍、应用与实施1.实施playbook1.1AnsiblePlaybook与临时命令1.2格式化AnsiblePlaybook1.3运行playbook1.4提高输出的详细程度1.5语法验证1.6执行空运行2.实施多个play2.1缩写多个play2.2play中的远程用户和......
  • 图像分类实战:深度学习在CIFAR-10数据集上的应用
    1.前言        图像分类是计算机视觉领域的一个核心任务,算法能够自动识别图像中的物体或场景,并将其归类到预定义的类别中。近年来,深度学习技术的发展极大地推动了图像分类领域的进步。CIFAR-10数据集作为计算机视觉领域的一个经典小型数据集,为研究者提供了一个理想的......
  • CrossOver2024最新免费版虚拟机软件 Mac和Linux系统上运行Windows 应用/游戏 CrossOve
    CrossOver是一款由CodeWeavers公司开发的,运行在Mac和Linux操作系统下,能够模拟Windows系统应用运行环境的软件。它不需要用户单独安装Windows操作系统,就能让Windows平台上的应用程序在Mac和Linux上顺畅运行。CrossOver在技术上使用了Wine(Windows模拟器)的代码,通过提供一个兼容层,......
  • 【Java系列】 Web开发 | 基于jQuery的Ajax应用
    原创:清华计算机学堂基于jQuery的Ajax应用01、jQuery简介jQuery是一个免费、开源、兼容多浏览器的JavaScript库,其核心理念是:writeless,domore(写得更少,做得更多)。jQuery于2006年1月由美国人JohnResig在纽约的barcamp发布,吸引了来自世界各地的众多JavaScript高手加入,由DaveMe......