【洛谷 P8720】[蓝桥杯 2020 省 B2] 平面切分 题解(计算几何+集合+向量)

[蓝桥杯 2020 省 B2] 平面切分

题目描述

平面上有 N N N 条直线, 其中第 i i i 条直线是 y = A i ⋅ x + B i y=A_{i} \cdot x+B_{i} y=Aix+Bi

请计算这些直线将平面分成了几个部分。

输入格式

第一行包含一个整数 N N N

以下 N \mathrm{N} N 行, 每行包含两个整数 A i , B i A_{i}, B_{i} Ai,Bi

输出格式

一个整数代表答案。

样例 #1

样例输入 #1

3
1 1
2 2
3 3

样例输出 #1

6

提示

对于 50 % 50 \% 50% 的评测用例, 1 ≤ N ≤ 4 , − 10 ≤ A i , B i ≤ 10 1 \leq N \leq 4,-10 \leq A_{i}, B_{i} \leq 10 1N4,10Ai,Bi10

对于所有评测用例, 1 ≤ N ≤ 1000 , − 1 0 5 ≤ A i , B i ≤ 1 0 5 1 \leq N \leq 1000,-10^5 \leq A_{i}, B_{i} \leq 10^5 1N1000,105Ai,Bi105

蓝桥杯 2020 第二轮省赛 B 组 I 题


思路

首先,定义几个数据类型和常量。ll定义为long longpii定义为pair<double, double>

读取直线的数量 n n n。然后,定义一个set来存储所有的直线,每条直线用一个二元组(斜率和截距)表示。这里使用set的目的是为了保证所有的直线都是唯一的,因为set会自动删除重复的元素。接着,将set中的直线复制到一个vector中,方便后续的遍历。

然后,定义一个变量ans来存储最终的结果。初始值设为2,因为一条直线至少可以将平面分为两个部分。

接下来,遍历vector中的每一条直线,对于每一条直线,都定义一个新的set来存储与其他直线的交点。这里使用set的目的是为了自动删除重复的交点。

在计算交点时,首先检查两条直线是否平行,如果平行,则没有交点,直接跳过。否则,通过两条直线的斜率和截距计算出交点,并将交点添加到set中。

最后,将set的大小加1后加到ans中。这是因为,每增加 n n n个交点,就会多出 n + 1 n+1 n+1个新的部分。

遍历完所有的直线后,输出ans,这就是最终的结果。

注意

因为斜率等参数不一定是整数,应该使用 double 来存储数据,否则无法通过测试点。


AC代码

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
#define mp make_pair
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;
using pii = pair<double, double>;const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;int n;
set<pii> s1;
vector<pii> v1;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) {double a, b;cin >> a >> b;s1.insert({a, b});}for (const auto i : s1) {v1.push_back(i);}// 一条线能分出两个部分ll ans = 2;for (int i = 1; i < v1.size(); i++) {set<pii> s2;for (int j = i - 1; j >= 0; j--) {double k1 = v1[i].first;double k2 = v1[j].first;double b1 = v1[i].second;double b2 = v1[j].second;if (k1 == k2) {// 平行,无交点continue;}// 求交点double x = (b2 - b1) / (k2 - k1);double y = k1 * x + b1;s2.insert({x, y});}// 每多n个交点,就多n+1个部分ans += s2.size() + 1;}cout << ans << "\n";return 0;
}

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

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

相关文章

阿里巴巴中国站获得商品快递费用 API 返回值说明

一、应用场景 阿里巴巴中国站获得商品快递费用 API&#xff08;1688.item_fee&#xff09;通常用于查询商品的快递费用。这个API的应用场景包括但不限于以下几个方面&#xff1a; 1、电商平台&#xff1a;在电商平台上&#xff0c;当用户购买商品时&#xff0c;需要知道商品的…

LLM(十一)| Claude 3:Anthropic发布最新超越GPT-4大模型

2024年3月4日&#xff0c;Anthropic发布最新多模态大模型&#xff1a;Claude 3系列&#xff0c;共有Haiku、Sonnet和Opus三个版本。 Opus在研究生水平专家推理、基础数学、本科水平专家知识、代码等10个维度&#xff0c;超过OpenAI的GPT-4。 Haiku模型更注重效率&#xff0c;能…

uniapp模仿下拉框实现文字联想功能 - uniapp输入联想(官方样式-附源码)

一、效果 废话不多说&#xff0c;上效果图&#xff1a; 在下方的&#xff1a; 在上方的&#xff1a; 二、源码 一般是个输入框&#xff0c;输入关键词&#xff0c;下拉一个搜索列表。 ElementUI有提供<el-autocomplete>&#xff0c;但uniapp官网没提供这么细&#x…

15个经典面试问题及回答思路,小白以及计算机类学生的福音

前言 这几年在Java工程师招聘时&#xff0c;会看到很多人的简历都写着使用了Spring Cloud做微服务实现&#xff0c;使用Docker做自动化部署&#xff0c;并且也会把这些做为自己的亮点。而比较有趣的这其中以小公司出来的人为绝大多数&#xff0c;大的公司出来的人简历上倒是很…

自动化测试基础——Pytest框架之YAML详解以及Parametrize数据驱动

文章目录 一、YAML详解1.YAML作用2.YAML语法结构3.YAML数据类型3.1.对象3.2.数组3.3.标量 4.YAML的引用5.YAML类型转换 二、YAML的读写与清空1.YAML的读2.YAML的写3.YAML的清空 三、pytest的parametrize简单数据驱动四、pytest的parametrize结合yaml实现数据驱动五、解决pytest…

rabbitmq基础(1)

1、背景 能实现消息队列的框架软件有很多&#xff0c;kafka、rabbitmq、RocketMq、activeMq、Redis&#xff08;非专业&#xff09;&#xff0c;各有各的特点和优缺点。但是之前的公司数据需求规模并非很大&#xff0c;所以采用rabbitmq作为消息队列。 2、rabbitMq的基础架构…

docker单节点搭建在线商城

本文档使用到的软件包以上传到资源中 目录 1. 创建容器并配置基础内容 1.1 将gpmall-repo上传到容器中 1.2 添加yum源 2. 安装基础服务 2.1 安装JAVA环境 2.2 安装Redis缓存服务 2.3 安装Elasticsearch服务 2.4 安装Nginx服务 2.5 安装MariaDB数据库 2.6 安…

LeetCode Python - 36.有效的数独

目录 题目答案运行结果 题目 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 &#xff0c;验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。&#xff08…

【设计模式】(二)设计模式六大设计原则

一、 设计原则概述 设计模式中主要有六大设计原则&#xff0c;简称为SOLID &#xff0c;是由于各个原则的首字母简称合并的来(两个L算一个,solid 稳定的)&#xff0c;六大设计原则分别如下&#xff1a; ​ 1、单一职责原则&#xff08;Single Responsibitity Principle&#…

Fiddler入门:下载、安装、配置、抓包、customize rules

一、fiddler下载安装 安装包下载链接&#xff1a;https://www.telerik.com/download/fiddler 随便选个用途&#xff0c;填写邮箱&#xff0c;地区选择China&#xff0c;勾选“I accept the Fiddler End User License Agreement”&#xff0c;点击“DownLoad for windows”&…

element loading遮罩层添加按钮

<el-table v-loading"loadingText" element-loading-text"拼命加载中" :data"tableData" :tableColumn"tableColumn" :span-method"objectSpanMethod" border :cell-style"cellStyle" :header-cell-style"…

备考2024年小学生古诗文大会:历年真题15题练习和独家解析

如何提高小学生古诗词的知识&#xff1f;如何激发小学生古诗词的学习兴趣&#xff1f;如何提高小学古诗词的学习成绩&#xff1f;如何备考2024年小学生古诗文大会&#xff1f;...如果你也在关心和这些问题&#xff0c;我的建议是参加每年一度的小学生古诗词大会&#xff08;免费…

安卓类加载机制

目录 一、ClassLoader介绍二、双亲委托机制三、类的加载过程 一、ClassLoader介绍 任何一个 Java 程序都是由一个或多个 class 文件组成&#xff0c;在程序运行时&#xff0c;需要将 class 文件加载到 JVM 中才可以使用&#xff0c;负责加载这些 class 文件的就是 Java 的类加…

【深圳五兴科技】Java后端面经

本文目录 写在前面试题总览1、java集合2、创建线程的方式3、对spring的理解4、Spring Boot 和传统 Spring 框架的一些区别5、springboot如何解决循环依赖6、对mybatis的理解7、缓存三兄弟8、接口响应慢的处理思路9、http的状态码 写在前面 关于这个专栏&#xff1a; 本专栏记录…

iOS消息转发流程

当向Objc对象发送消息时&#xff0c;如果找到对象对应的方法&#xff0c;就会进入消息转发流程&#xff0c;给开发者提供一些最后的机会处理消息无法发送问题&#xff0c;以免出现程序崩溃。 1. 回调对象的resolveInstanceMethod方法&#xff0c;在这个方法中&#xff0c;允许开…

LeetCode 热题 100 | 图论(二)

目录 1 基础知识 1.1 什么是拓扑排序 1.2 如何进行拓扑排序 1.3 拓扑排序举例 2 207. 课程表 3 210. 课程表 II 菜鸟做题&#xff0c;语言是 C 1 基础知识 1.1 什么是拓扑排序 含义&#xff1a;根据节点之间的依赖关系来生成一个有序的序列。 应用&#xff1a…

Mybatis实现分页查询数据(代码实操讲解)

在MyBatis中实现分页查询的常见方式有两种&#xff1a;使用MyBatis内置的分页插件如PageHelper&#xff0c;或者手动编写分页的SQL语句。下面我将为你提供两种方式的示例代码。 使用PageHelper分页插件 首先&#xff0c;确保你的项目中已经添加了PageHelper的依赖。在Maven项…

gpt批量工具,gpt批量生成文章工具

GPT批量工具在今天的数字化时代扮演着越来越重要的角色&#xff0c;它们通过人工智能技术&#xff0c;可以自动批量生成各种类型的文章&#xff0c;为用户提供了便利和效率。本文将介绍5款不同的GPT批量工具&#xff0c;并介绍一款知名的147GPT生成工具&#xff0c;以及另外一款…

js SheetJS 合并表格导出到同一个excel中

最近有个需求,我在一个页面显示了4个表格, 然后合并导出到excel文件中 四个表,四个sheet,一个excel文件 最后导出时这样: 实现: 1,页面有个导出的checkbox,勾选则导出,不勾选不处理 2,在一个函数中,集中处理四个表数据获取,并将结果返回出来 //获取数据后返回为…

代码随想录算法训练营第三十四天| 860.柠檬水找零 、406.根据身高重建队列 、452. 用最少数量的箭引爆气球

文章目录 1.柠檬水找零2.根据身高重建队列3.用最少数量的箭引爆气球 1.柠檬水找零 在柠檬水摊上&#xff0c;每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品&#xff0c;&#xff08;按账单 bills 支付的顺序&#xff09;一次购买一杯。 每位顾客只买一杯柠檬水&#xf…