当前位置: 首页 > 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;并且我们的卡与计算机不兼容。 适配器是两个不兼容实体之间的转换器。适配器模式是一种结构模…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...