当前位置: 首页 > news >正文

【算法入门教育赛2】C.曼哈顿种类 C++题解与代码

比赛地址:https://www.starrycoding.com/contest/6

题目描述

e e e知道在武汉有 n n n家自助店,第 i i i个自助店用坐标 ( x i , y i ) (x_i, y_i) (xi,yi)表示,因为武汉的街道都是互相垂直的,现在他想知道所有自助店之间的曼哈顿距离有多少种?

曼哈顿距离: ( x 1 , y 1 ) (x_1, y_1) (x1,y1) ( x 2 , y 2 ) (x_2, y_2) (x2,y2)的曼哈顿距离为: ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ |x_1 - x_2| + |y_1 - y_2| x1x2+y1y2

注意:可能有多个自助点在同一个坐标,那么它们之间的曼哈顿距离为 0 0 0

输入格式

第一行一个整数 T T T表示测试用例个数。 ( 1 ≤ T ≤ 1000 ) (1 \le T \le 1000) (1T1000)

对于每组测试用例:

一行一个整数 n ( 2 ≤ n ≤ 1 0 3 ) n(2 \le n \le 10^3) n(2n103)

接下来 n n n行,第 i i i行表示第 i i i个自助店的坐标 ( x i , y i ) , ( − 1 0 9 ≤ x i , y i ≤ 1 0 9 ) (x_i, y_i), (-10^9 \le x_i, y_i \le 10^9) (xi,yi),(109xi,yi109)

数据保证 ∑ n ≤ 1 0 3 \sum n \le 10^3 n103

输出格式

对于每组测试用例,输出一个整数表示答案。

输入样例1

2
3
0 0
0 1
1 1
2
0 0
1 1

输出样例1

2
1

解释

在样例 1 1 1中,共有 { 1 , 1 , 2 } \{1, 1, 2\} {1,1,2}三个曼哈顿距离,共 2 2 2种。

题解

枚举所有点对,计算其曼哈顿距离后放入 s e t set set中计算 s i z e size size,或放入数组中排序去重。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 1e3 + 9;ll x[N], y[N];ll getabs(ll x) { return x < 0 ? -x : x; }void solve()
{int n;cin >> n;for (int i = 1; i <= n; ++i)cin >> x[i] >> y[i];set<ll> st;for (int i = 1; i <= n; ++i)for (int j = i + 1; j <= n; ++j){st.insert(getabs(x[i] - x[j]) + getabs(y[i] - y[j]));}cout << st.size() << '\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _;cin >> _;while (_--)solve();return 0;
}

相关文章:

【算法入门教育赛2】C.曼哈顿种类 C++题解与代码

比赛地址&#xff1a;https://www.starrycoding.com/contest/6 题目描述 牢 e e e知道在武汉有 n n n家自助店&#xff0c;第 i i i个自助店用坐标 ( x i , y i ) (x_i, y_i) (xi​,yi​)表示&#xff0c;因为武汉的街道都是互相垂直的&#xff0c;现在他想知道所有自助店之间…...

Electron使用 SQLite

在客户端开发中&#xff0c;无论是 PC 端&#xff0c;还是手机端&#xff0c;为了能够访问离线数据&#xff0c;数据经常需要保存到本地&#xff0c;IndexDB 可以用于存储本地数据&#xff0c;IndexDB 是一个对象存储&#xff0c;数据是以 key:value 的形式进行存储和访问的&am…...

怎样的跨网软件,可以实现网间数据的安全收发?

网络隔离已是较为常见的网络安全保护措施&#xff0c;比如防火墙、网闸、VLAN&#xff0c;云桌面虚拟环境等方面进行隔离。像一些科技研发型企业&#xff0c;不仅仅是内外网隔离&#xff0c;甚至还划分办公网、研发网、测试网、生产网等&#xff0c;防止研发资料、设计资料等敏…...

Sora惊艳亮相:AI技术掀起创作革命,影视产业迎来新风貌!

Sora平台近期发布了名为"Sora首次印象"的更新&#xff0c;为用户带来了令人瞩目的变化。该更新不仅展示了Sora平台的发展方向&#xff0c;还介绍了其在电影制作、广告宣传等领域的潜在应用。 同时&#xff0c;Sora的首席执行官Sam Altman与好莱坞影视工作室进行了会…...

Mac电脑安装打开APP显示问题已损坏 问题解决

当MAC电脑安装完软件打开时&#xff0c;显示文件已损坏&#xff0c;无法打开。搜了很多教程终于找到解决方案&#xff0c;记录下方便以后再用。 我的mac电脑是intel芯片的&#xff0c;如果你遇到这个问题&#xff0c;可以参考我的这个方案。 1.首先当打开软件后出现 “xx软件已…...

AI 数据观 | TapData Cloud + MongoDB Atlas:大模型与 RAG 技术有机结合,落地实时工单处理智能化解决方案

本篇为「AI 数据观」系列文章第二弹&#xff0c;在这里&#xff0c;我们将进一步探讨 AI 行业的数据价值。以 RAG 的智能工单应用场景为例&#xff0c;共同探索如何使用 Tapdata Cloud MongoDB Atlas 实现具备实时更新能力的向量数据库&#xff0c;为企业工单处理的智能化和自…...

Vulnhub靶机随笔-Hacksudo_Aliens

Vulnhub靶机Hacksudo_Aliens详解 攻击机Kali IP:192.168.3.44 靶机 IP:未知 系统:未知 A.信息收集 扫描靶机存活性 确定IP地址 1.命令:arp-scan -l 扫描靶机开放端口及其服务版本信息 2.命令 nmap -A -p- -sV 靶机IP地址 靶机开放三个端口,22ssh端口,80web端…...

抖店选品都怎么选品?什么样的产品更吸引人,更具有购买力?

大家好&#xff0c;我是电商花花。 抖店选品一直都是我们无货源商家的核心问题&#xff0c;不管是出单、还是爆单&#xff0c;店铺想要有销量的前提下都是选品。 很多人一上来就是就是选品&#xff0c;没有选品经验还瞎选品&#xff0c;结果到最后选了一堆出单的产品&#xf…...

将来会是Python、Java、Golang三足鼎立吗?

在开始前我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「 Java的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&#xff01; 软件工程里没有银弹&#xff…...

Java入门基础学习笔记16——运算符

package cn.ensource.operator;public class OperatorDemo1 {public static void main(String[] args) {// 目标&#xff1a;掌握基本的算术运算符的使用int a 10;int b 2;System.out.println(a b);System.out.println(a - b);System.out.println(a * b); // 20System.out.…...

golang中三种线程安全的MAP

一、map 是什么 map 是 Go 中用于存储 key-value 关系数据的数据结构&#xff0c;类似 C 中的 map&#xff0c;Python 中的 dict。Go 中 map 的使用很简单&#xff0c;但是对于初学者&#xff0c;经常会犯两个错误&#xff1a;没有初始化&#xff0c;并发读写。 1、未初始化的…...

C++笔试强训day16

目录 1.字符串替换 2.神奇数 3.DNA序列 1.字符串替换 链接 简单的遍历替换即可&#xff1a; class Solution { public:string formatString(string str, vector<char>& arg) {string ret;int k 0;for (int i 0; i < str.size(); i){if (str[i] %){ret arg…...

spsr 的恢复出错,导致 thumb 指令集的 it 条件运行指令运行异常,清晰的调试思路帮助快速解决问题

记一次调试过程 这是一个在 arm 架构上的 RTOS 上的调试过程。问题现象为使用 thumb 指令集的 libgcc 库的情况下&#xff0c;浮点运算随机出错。经过一番追踪调试&#xff0c;逐步缩小问题范围&#xff0c;最后定位问题&#xff0c;成功解决。 场景 在某款的国产 RTOS 上&a…...

mysql binlog 如何区分db

binlog不是InnoDB存储引擎特有的日志文件&#xff0c;是属于mysql server自己的日志文件。 提交事务的时候&#xff0c;同时会写入binlog 在MySQL中&#xff0c;Binary Log&#xff08;binlog&#xff09;记录了数据库更改操作的所有细节&#xff0c;对于实现数据复制、恢复以…...

ESP32 IDF linux下开发环境搭建

文章目录 介绍升级Python环境下载Python包配置编译环境及安装Python设置环境变量 ESPIDF环境搭建下载esp-idf 代码编译等待下载烧录成功查看串口打印 介绍 esp32 官方文档给的不是特别详细 参考多方资料 最后才完成开发 主要问题在于github下载的很慢本教程适用于ubuntu deban…...

光伏电站智能管理平台功能全面介绍

一、介绍 光伏电站智能管理平台专门为了光伏电站服务的融合了项目沟通、在线设计、施工管理、运维工单等多智能光伏管理系统&#xff0c;可以满足光伏电站建设前期沟通、中期建设和后续维护的一体化智能平台&#xff0c;同时通过组织架构对企业员工进行线上管理和数据同步&…...

SSL证书 购买流程

在购买SSL证书之前&#xff0c;需要知道一点相关的知识&#xff0c;通常包括以下几个环节&#xff1a; 一、确定需求 1、根据需要保护的域名数量&#xff0c;在以下三类中选择合适的证书类型&#xff1a; 单域名证书&#xff0c;只对一个域名&#xff08;例如abc.com&#x…...

C++|二叉搜索树

一、二叉搜索树的概念 二叉搜索树又称为二叉排序树&#xff0c;它或者是一颗空树&#xff0c;或者是具有以下性质的二叉树&#xff1a; 若它的左子树不为空&#xff0c;则左子树上所有节点的值小于根节点的值若它的右子树不为空&#xff0c;则右子树上所有节点的值都大于根结…...

网页html版面分析-- BeauifulSoup(python 文档解析提取)

介绍 BeauifulSoup 是一个可以从HTML或XML 文件中提取数据的python库&#xff1b;它能通过转换器实现惯用的文档导航、查找、修改文档的方式。 BeauifulSoup是一个基于re开发的解析库&#xff0c;可以提供一些强大的解析功能&#xff1b;使用BeauifulSoup 能够提高提取数据的效…...

第五十八节 Java设计模式 - 适配器模式

Java设计模式 - 适配器模式 我们在现实生活中使用适配器很多。例如&#xff0c;我们使用存储卡适配器连接存储卡和计算机&#xff0c;因为计算机仅支持一种类型的存储卡&#xff0c;并且我们的卡与计算机不兼容。 适配器是两个不兼容实体之间的转换器。适配器模式是一种结构模…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...