【数据结构•并查集】矩形

题目描述

在一个平面上有n个矩形。每个矩形的边都平行于坐标轴并且都具有值为整数的顶点。我们用如下的方式来定义块。
每一个矩形都是一个块。
如果两个不同的矩形有公共线段,那么它们就组成了一个新的块来覆盖它们原来的两个块。
例子:
在图1中的矩形组成了两个不同的块。
图1:

1556645547127918594.bmp

在图2中的矩形组成了单独一个块。

1556645599288283137.bmp

任务:
写一个程序:
读入矩形的个数以及它们的顶点。
找出这些矩形形成的不同的块的个数。

输入输出格式

输入格式:

第一行又一个整数n,表示矩形的个数。接下来的n行描述矩形的顶点,每个矩形用四个数来描述:左下顶点坐标(x,y)与右上顶点坐标(x,y)。每个矩形的坐标都是不超过10000的非负整数.

输出格式:

仅有一个整数---表示由给定矩形组成的不同的块的个数。

输入输出样例

输入样例#1:

9
0 3 2 6
4 5 5 7
4 2 6 4
2 0 3 2
5 3 6 4
3 2 5 3
1 4 4 7
0 0 1 4
0 0 4 1

输出样例#1:

2

提示信息

1 <= n <=7000

算法分析:
 

显然,该题可由并查集来做。

暴力枚举每两个矩形是否在同一集合,若非,则将其所在集合合并。

时间复杂度约为O(n^2/2)如果没有“/2”可能超时

详细说明在代码中解释:
 

#include<bits/stdc++.h>
using namespace std;
struct ju{int leupx;int leupy;int ridox;int ridoy;
}zhen[7001];
struct win{int l;int r;int t;int b;
};//两个矩形交界的上下左右边界
int f[7010],ans=0;
int find(int k)
{if(f[k]==k) return k;else return f[k]=find(f[k]);
}
bool pd(int i,int j)
{win tmp;tmp.l=max(zhen[i].leupy,zhen[j].leupy);tmp.r=min(zhen[i].ridoy,zhen[j].ridoy);tmp.t=max(zhen[i].leupx,zhen[j].leupx);tmp.b=min(zhen[i].ridox,zhen[j].ridox);if(tmp.r==tmp.l&&tmp.b>tmp.t) return 1;if(tmp.r>tmp.l&&tmp.b==tmp.t) return 1;//交界是一条线也算相交if((tmp.r<=tmp.l)||(tmp.b<=tmp.t)) return 0;//无交界return 1;//交界是一个点
}
int main()
{int n;cin>>n;for(int i=1;i<=n;i++) f[i]=i;for(int i=1;i<=n;i++) scanf("%d%d%d%d",&zhen[i].leupx,&zhen[i].leupy,&zhen[i].ridox,&zhen[i].ridoy);for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) if((pd(i,j))==1) if(find(i)!=find(j)) f[find(i)]=find(j);for(int i=1;i<=n;i++) if(find(f[i])==i) ans++;cout<<ans;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/89839.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【SpringCloud技术专题】「Resilience4j入门指南」(1)轻量级熔断框架的入门指南

基础介绍 Resilience4j是一款轻量级&#xff0c;易于使用的容错库&#xff0c;其灵感来自于Netflix Hystrix&#xff0c;但是专为Java 8和函数式编程而设计。轻量级&#xff0c;因为库只使用了Vavr&#xff0c;它没有任何其他外部依赖下。相比之下&#xff0c;Netflix Hystrix…

树莓派3B CSI摄像头配置

1.硬件连接 1、找到 CSI 接口(树莓派3B的CSI接口在HDMI接口和音频口中间)&#xff0c;需要拉起 CSI 接口挡板,如下&#xff1a; 2、将摄像头排线插入CSI接口。记住&#xff0c;有蓝色胶带的一面应该面向音频口或者网卡方向&#xff0c; 确认方向并插紧排线&#xff0c;将挡板…

Tomcat+Http+Servlet

文章目录 1.HTTP1.1 请求和响应HTTP请求&#xff1a;请求行请求头请求体HTTP响应&#xff1a;响应行&#xff08;状态行&#xff09;响应头响应体 2. Apache Tomcat2.1 基本使用2.2 IDEA中创建 Maven Web项目2.3 IDEA中使用Tomcat 3. Servlet3.1 Servlet快速入门3.2 Servlet执行…

Scala函数式编程

概念 函数 一种具有名或匿名的操作。其代码直到被调用时才执行。在函数的定义中&#xff0c;可能有也可能没有引用外部的未绑定变量。 def 函数名([参数名: 参数类型],...) [: 返回值类型] {语句[return] 返回值 }函数声明的关键字是 def[参数名: 参数类型],…&#xff1a;…

如何使用SpringBoot 自定义转换器

&#x1f600;前言 本篇博文是关于SpringBoot 自定义转换器的使用&#xff0c;希望你能够喜欢&#x1f60a; &#x1f3e0;个人主页&#xff1a;晨犀主页 &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是晨犀&#xff0c;希望我的文章可以帮助到大家&#xff0c;您的…

简单谈谈 EMP-SSL:自监督对比学习的一种极简主义风

论文链接&#xff1a;https://arxiv.org/pdf/2304.03977.pdf 代码&#xff1a;https://github.com/tsb0601/EMP-SSL 其他学习链接&#xff1a;突破自监督学习效率极限&#xff01;马毅、LeCun联合发布EMP-SSL&#xff1a;无需花哨trick&#xff0c;30个epoch即可实现SOTA 主要…

Vue3 setup tsx 子组件向父组件传值 emit

需求&#xff1a;Vue3 setup 父组件向子组件传值&#xff0c;子组件接收父组件传入的值&#xff1b;子组件向父组件传值&#xff0c;父组件接收的子组件传递的值。 父组件&#xff1a;parent.tsx&#xff1a; import { defineComponent, ref, reactive } from vue; import To…

【STM32】利用CubeMX对FreeRTOS用按键控制任务

对于FreeRTOS中的操作&#xff0c;最常用的就是创建、删除、暂停和恢复任务。 此次实验目标&#xff1a; 1.创建任务一&#xff1a;LED1每间隔1秒闪烁一次&#xff0c;并通过串口打印 2.创建任务二&#xff1a;LED2每间隔0.5秒闪烁一次&#xff0c;并通过串口打印 3.创建任…

【工作记录】mysql中实现分组统计的三种方式

前言 实际工作中对范围分组统计的需求还是相对普遍的&#xff0c;本文记录下在mysql中通过函数和sql完成分组统计的实现过程。 数据及期望 比如我们获取到了豆瓣电影top250&#xff0c;现在想知道各个分数段的电影总数. 表数据如下: 期望结果: 实现方案 主要思路是根据s…

SpringMVC拦截器

1.拦截器简介 拦截器&#xff08;Interceptor&#xff09;是一种动态拦截方法调用的机制&#xff0c;在SpringMVC中动态拦截控制器方法的执行 作用: 在指定的方法调用前后执行预先设定的代码 阻止原始方法的执行 总结&#xff1a;拦截器就是用来做增强 看完以后&#xff0…

【在一个升序数组中插入一个数仍升序输出】

在一个升序数组中插入一个数仍升序输出 题目举例&#xff1a; 有一个升序数组nums&#xff0c;给一个数字data&#xff0c;将data插入数组nums中仍旧保证nums升序&#xff0c;返回数组中有效元素个数。 比如&#xff1a;nums[100] {1, 2, 3, 5, 6, 7, 8, 9} size 8 data 4 …

elementUi表单恢复至初始状态并不触发表单验证

elementUi表单恢复至初始状态并不触发表单验证 1.场景再现2.解决方法 1.场景再现 左侧是树形列表&#xff0c;右侧是显示节点的详情&#xff0c;点击按钮应该就是新增一个规则的意思&#xff0c;表单内容是没有改变的&#xff0c;所以就把需要把表单恢复至初始状态并不触发表单…

正则表达式试炼

序 我希望在这里列出我很多想写的正则表达式&#xff0c;很多我想写&#xff0c;但是不知道怎么写的。分享点滴案例。未来这个文章会越来越长 前言 互联网时代&#xff0c;除了文本还有更好的学习方式&#xff0c;下面是几个不错的练习网站&#xff0c;如果你想系统地学习&a…

深入了解Linux运维的重要性与最佳实践

Linux作为开源操作系统的代表&#xff0c;在企业级环境中的应用越来越广泛。而在保障Linux系统的正常运行和管理方面&#xff0c;Linux运维显得尤为关键。本文将介绍Linux运维的重要性以及一些最佳实践&#xff0c;帮助读者更好地了解和掌握Linux系统的运维技巧。 首先&#xf…

如何更快地执行 Selenium 测试用例?

前言&#xff1a; 当我们谈论自动化时&#xff0c;首先想到的工具之一是 Selenium。我们都知道Selenium WebDriver 是一个出色的 Web 自动化工具。实施Selenium 自动化测试的主要原因是加速 selenium 测试。在大多数情况下&#xff0c;Selenium 的性能比手动的要好得多。但是&…

离线安装vscode插件,导出 Visual Studio Code 的扩展应用,并离线安装

在没有网络的情况下&#xff0c;如何安装vscode插件 1.使用之前电脑安装过的插件包 Visual Studio Code 的扩展应用安装位置在文件夹 .vscode/extensions 下。不同平台&#xff0c;它位于&#xff1a; Windows %USERPROFILE%\.vscode\extensions Mac ~/.vscode/extensions L…

C字符串练习题(6.3.1)

编写一个程序&#xff0c;从键盘上读入一个小于1000的正整数&#xff0c;然后创建并输出一个字符串&#xff0c;说明该整数的值。例如&#xff0c;输入941&#xff0c;程序产生的字符串是“Nine hundred and forty one”。 #include<stdlib.h> #include<string.h>…

【JAVA】我们常常谈到的方法是指什么?

个人主页&#xff1a;【&#x1f60a;个人主页】 系列专栏&#xff1a;【❤️初识JAVA】 文章目录 前言方法方法的分类方法的定义方法调用方法重载 前言 在之前的文章中我们总是会介绍到类中的各式各样的方法&#xff0c;也许在应用中我们对它已经有了初步的了解&#xff0c;今…

# ⛳ Docker 安装、配置和详细使用教程-Win10专业版

目录 ⛳ Docker 安装、配置和详细使用教程-Win10专业版&#x1f69c; 一、win10 系统配置&#x1f3a8; 二、Docker下载和安装&#x1f3ed; 三、Docker配置&#x1f389; 四、Docker入门使用 ⛳ Docker 安装、配置和详细使用教程-Win10专业版 &#x1f69c; 一、win10 系统配…

使用docker快速搭建wordpress服务,并指定域名访问

文章目录 引入使用docker快速跑起服务创建数据库安装wordpress服务配置域名 引入 wordpress是一个基于PHP语言编写的开源的内容管理系统&#xff08;CMS&#xff09;&#xff0c;它有丰富的插件和主题&#xff0c;可以非常简单的创建各种类型的网站&#xff0c;包括企业网站、…