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

【算法训练营】凸包,图(Python实现)

凸包


描述

给定n个二维平面上的点,求他们的凸包。

输入

第一行包含一个正整数n。

接下来n行,每行包含两个整数x,y,表示一个点的坐标。

输出

令所有在凸包极边上的点依次为p1,p2,...,pm(序号),其中m表示点的个数,请输出以下整数:

(p1 × p2 × ... × pm × m) mod (n + 1)

样例1输入

10
7 9
-8 -1
-3 -1
1 4
-3 9
6 -4
7 5
6 6
-6 10
0 8

样例1输出

7

样例1解释

所以答案为(9 × 2 × 6 × 7 × 1 × 5) % (10 + 1) = 7

样例2

请查看下发文件内的sample2_input.txt和sample2_output.txt。

限制

3 ≤ n ≤ 10^5

所有点的坐标均为范围(-10^5, 10^5)内的整数,且没有重合点。每个点在(-10^5, 10^5) × (-10^5, 10^5)范围内均匀随机选取

极边上的所有点均被视作极点,故在输出时亦不得遗漏

时间:4 sec

空间:512 MB

代码实现 

from typing import List, Tupleclass Ip:def __init__(self, x:int = 0, y:int = 0, i:int = 0) -> None:self.x = xself.y = yself.i = idef __sub__(self, other: 'Ip') -> 'Ip':return Ip(self.x - other.x, self.y - other.y)@classmethoddef read(cls, index: int) -> 'Ip':x, y = map(int, input().strip().split())return cls(x, y, index)def cross_product(a: Ip, b: Ip) -> int:return a.x * b.y - a.y * b.xdef convex(a: List[Ip]) -> List[Ip]:a.sort(key=lambda p: (p.x, p.y))b = []for p in a:while len(b) > 1:if cross_product(b[-1] - b[-2], p - b[-2]) <= 0:breakb.pop()b.append(p)temp = b[:]for p in reversed(a[:-1]):while len(b) > len(temp):if cross_product(b[-1] - b[-2], p - b[-2]) <= 0:breakb.pop()b.append(p)return b[:-1]if __name__ == "__main__":n = int(input().strip())a = [Ip.read(i + 1) for i in range(n)]b = convex(a)ans = len(b)for p in b:ans = (ans * p.i) % (n + 1)print(ans)


描述

一个数列 a 称为合法的当且仅对于所有的位置 i, j(i < j ≤ n),都不存在一条从 aj 点连向 ai 的有向边。现在有很多个有向无环图,请你判断每个图是否只存在唯一的合法数列。

输入

输入的第一行包含一个正整数 T ,表示数据组数。

对于每组数据,第一行包含两个正整数 n, m,表示图的节点个数和边数。

接下来 m 行,每行包含两个正整数 x, y(x, y ≤ n),表示这个图有一条从 x 到 y 的有向边。

保证没有自环和重边。

输出

输出 T 行,若所给的图存在唯一的合法数列,输出 1,否则输出 0。

样例1输入

2
3 2
1 2
2 3
3 2
1 2
1 3

样例1输出

1
0

样例1解释

第一个图只有一个合法数列:1、2、3;

第二个图有两个合法数列:1、2、3 或者 1、3、2。

样例2

请查看下发文件内的sample2_input.txt和sample2_output.txt。

限制

对于50%的数据,n, m ≤ 100;

对于100%的数据,T ≤ 100, n, m ≤ 10000。

时间:4 sec

空间:512 MB

提示

[本题就是判断一个有向无环图是否存在唯一的拓扑序列。]

[回忆一下求拓扑序列是如何做的:每一次都取一个入度为0的点,将这个点取出来放进拓扑序列里,然后将这个点连向的所有点的入度减去1。]

[可以发现,在“每一次都取一个入度为0”这一步,若入度为0的点数多于1个,则显然拓扑序不唯一。]

[因此按照这个拓扑序算法做一遍就好。]

代码实现 

from collections import dequedef has_unique_topological_order(n, m, edges):in_degrees = [0] * (n + 1)adj_list = [[] for _ in range(n + 1)]for x, y in edges:in_degrees[y] += 1adj_list[x].append(y)zero_degree_queue = deque()for i in range(1, n + 1):if in_degrees[i] == 0:zero_degree_queue.append(i)count = 0while zero_degree_queue:if len(zero_degree_queue) > 1:return 0node = zero_degree_queue.popleft()count += 1for neighbor in adj_list[node]:in_degrees[neighbor] -= 1if in_degrees[neighbor] == 0:zero_degree_queue.append(neighbor)return 1 if count == n else 0def main():T = int(input())for _ in range(T):n, m = map(int, input().split())edges = [tuple(map(int, input().split())) for _ in range(m)]print(has_unique_topological_order(n, m, edges))if __name__ == "__main__":main()

相关文章:

【算法训练营】凸包,图(Python实现)

凸包 描述 给定n个二维平面上的点&#xff0c;求他们的凸包。 输入 第一行包含一个正整数n。 接下来n行&#xff0c;每行包含两个整数x,y&#xff0c;表示一个点的坐标。 输出 令所有在凸包极边上的点依次为p1,p2,...,pm&#xff08;序号&#xff09;&#xff0c;其中m表…...

webpack5零基础入门-6webpack处理图片资源

1.在webpack5中file-loader和url-loader为内置模块 通过在加载器中配置rule即可激活 {test: /\.(png|jpe?g|gif|webp)$/,type: asset} 2.使用webpack进行打包 执行npx webpack 可以看到图片资源打包后都被放到了dist文件目录下 3.使用webpack进行图片格式转换为base64 优势…...

计算机基础知识QA

目录 数据库 --mysql 关联查询 唯一索引如何创建&#xff0c;语句 更新表字段语句 查看字段类型 --redis 使用场景 数据结构 设置超时时间 linux 常用命令 发布版本 安装一个东西&#xff0c;发现一个东西安装的很慢&#xff0c;如何切换ip地的源&#xff1f;-&g…...

微信小程序一次性订阅requestSubscribeMessage授权和操作详解

一次性订阅&#xff1a;用户订阅一次发一次通知 一、授权 — requestSubscribeMessage Taro.requestSubscribeMessage({tmplIds: [], // 需要订阅的消息模板的id的集合success (res) {console.log("同意授权", res)},fail(res) {console.log(拒绝授权, res)}})点击或…...

ARM 汇编指令:(三)运算处理指令

目录 一.add指令 二.sub指令 三.MUL指令 一.add指令 add用于执行实现两个寄存器或寄存机或寄存器与立即数的相加操作。它可以用于整数、浮点数等各种数据类型的加法运算。 ADD{cond}{S} Rd,操作数,操作数 1.不带进位加法指令add add r1, r2, #4 //r1 r2 4 add r1, r2 …...

【C++庖丁解牛】STL简介 | string容器初次见面

&#x1f341;你好&#xff0c;我是 RO-BERRY &#x1f4d7; 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f384;感谢你的陪伴与支持 &#xff0c;故事既有了开头&#xff0c;就要画上一个完美的句号&#xff0c;让我们一起加油 目录 1. 什么是STL2. STL的版本…...

记OnlyOffice的两个大坑

开发版&#xff0c;容器部署&#xff0c;试用许可已安装。 word&#xff0c;ppt&#xff0c;excel均能正常浏览。 自带的下载菜单按钮能用。 但config里自定义的downloadAs方法却不一而足。 word能正常下载&#xff0c;excel和ppt都不行。 仔细比对调试了代码。发现app.js…...

分享几个Google Chrome谷歌浏览器历史版本下载网站

使用selenium模块的时候&#xff0c;从官网下载的谷歌浏览器版本太高&#xff0c;驱动不支持&#xff0c;所以需要使用历史的谷歌浏览器版本 &#xff0c;这里备份一下以防找不到了。 驱动下载地址&#xff1a;https://registry.npmmirror.com/binary.html?pathchromedriver 文…...

备考2025年AMC8竞赛:吃透2000-2024年600道真题(免费赠送真题)

我们继续来随机看五道AMC8的真题和解析&#xff0c;根据实践经验&#xff0c;对于想了解或者加AMC8美国数学竞赛的孩子来说&#xff0c;吃透AMC8历年真题是备考最科学、最有效的方法之一。 即使不参加AMC8竞赛&#xff0c;吃透了历年真题600道和背后的知识体系&#xff0c;那么…...

考研复试C语言篇

第一章 概述 1.1什么是程序 为了让计算机执行某些操作或解决某个问题而编写的一系列有序指令的合集。 1.4C语言的特点 代码级别的跨平台&#xff1a;由于标准的存在&#xff0c;使得几乎同样的C代码可用于多种操作系统&#xff0c;也适用于多种机型。使允许直接访问物理地址…...

Docker架构深度解析:守护进程、客户端与存储驱动的协同作战(下)

&#x1f407;明明跟你说过&#xff1a;个人主页 &#x1f3c5;个人专栏&#xff1a;《Docker幻想曲&#xff1a;从零开始&#xff0c;征服容器宇宙》 &#x1f3c5; &#x1f516;行路有良友&#xff0c;便是天堂&#x1f516; 目录 四、命名空间和控制组 1、Linux命名空…...

【强化学习笔记一】初识强化学习(定义、应用、分类、性能指标、小车上山案例及代码)

文章目录 第1章 初识强化学习1.1 强化学习及其关键元素1.2 强化学习的应用1.3 强化学习的分类1.3.1 按任务分类1.3.2 按算法分类 1.4 强化学习算法的性能指标1.5 案例&#xff1a;基于Gym库的智能体/环境接口1.5.1 安装Gym库1.5.2 使用Gym库1.5.3 小车上山1.5.3.1 有限动作空间…...

安卓面试准备汇总

java相关 面试-java基础相关-CSDN博客 android 基础相关 安卓基础面试题-CSDN博客 kotlin相关 android pms,cms,wms相关知识 android fragmework层的知识 项目相关的...

C#+datax实现定时增量同步

要使用C#和DataX实现定时增量同步&#xff0c;你可以使用以下步骤&#xff1a; 1. 安装DataX&#xff1a;首先&#xff0c;确保你已经安装了DataX。你可以从DataX的官方仓库中获取最新版本。 2. 配置DataX 任务&#xff1a;创建一个DataX任务&#xff0c;定义源&#xff08;sou…...

VUE实现Provide的计算属性

通过此篇可以学到&#xff1a; 如何使用Providerinject进行“跨代”传值如何实现一个计算属性的Provider如何解决告警“injection "xxxxx" not found. ” 一、描述 目前需要创建一个计算属性传入Provide&#xff0c;并且能够被其他组件Inject 二、实现 父组件 .…...

Spring Schedule:Spring boot整合Spring Schedule实战讲解定时发送邮件的功能

&#x1f389;&#x1f389;欢迎光临&#xff0c;终于等到你啦&#x1f389;&#x1f389; &#x1f3c5;我是苏泽&#xff0c;一位对技术充满热情的探索者和分享者。&#x1f680;&#x1f680; &#x1f31f;持续更新的专栏《Spring 狂野之旅&#xff1a;从入门到入魔》 &a…...

Midjourney绘图欣赏系列(十)

Midjourney介绍 Midjourney 是生成式人工智能的一个很好的例子&#xff0c;它根据文本提示创建图像。它与 Dall-E 和 Stable Diffusion 一起成为最流行的 AI 艺术创作工具之一。与竞争对手不同&#xff0c;Midjourney 是自筹资金且闭源的&#xff0c;因此确切了解其幕后内容尚不…...

【C语言】人生重开模拟器

前言&#xff1a; 人生重开模拟器是前段时间非常火的一个小游戏&#xff0c;接下来我们将一起学习使用c语言写一个简易版的人生重开模拟器。 网页版游戏&#xff1a; 人生重开模拟器 (ytecn.com) 1.实现一个简化版的人生重开模拟器 &#xff08;1&#xff09; 游戏开始的时…...

船舶AIS监控网络-船位信息查询:实时查询船舶动态,服务于船舶安全航行管理、港口调度计划、物流、船代、货代。【AIS动态信息编写船舶轨迹】

文章目录 引言I 预备知识1.1 相关术语1.2 主要功能1.3 MongoDB和Es各自优势II 系统架构2.1 电子海图开源JavaScript包2.2 地图渲染库2.3 地图服务调用(天地图)2.4 在Elasticsearch(ES)中存储船舶轨迹数据III 数据同步方案3.1 基于 Binlog 实时同步3.2 数据迁移工具:Canal3.3…...

Axios 中的文件上传(Upload File)方法

Axios 提供了多种上传文件&#xff08;Upload File&#xff09;的方法&#xff0c;适用于不同的上传场景。以下是其中几种常用的方法&#xff1a; 1. 使用 FormData 对象FormData是一个用于创建表单数据的 API&#xff0c;可用于发送包含文件和其他表单数据的multipart/form-d…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

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

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

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

篇章二 论坛系统——系统设计

目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...

WebRTC调研

WebRTC是什么&#xff0c;为什么&#xff0c;如何使用 WebRTC有什么优势 WebRTC Architecture Amazon KVS WebRTC 其它厂商WebRTC 海康门禁WebRTC 海康门禁其他界面整理 威视通WebRTC 局域网 Google浏览器 Microsoft Edge 公网 RTSP RTMP NVR ONVIF SIP SRT WebRTC协…...

《Offer来了:Java面试核心知识点精讲》大纲

文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...

【版本控制】GitHub Desktop 入门教程与开源协作全流程解析

目录 0 引言1 GitHub Desktop 入门教程1.1 安装与基础配置1.2 核心功能使用指南仓库管理日常开发流程分支管理 2 GitHub 开源协作流程详解2.1 Fork & Pull Request 模型2.2 完整协作流程步骤步骤 1: Fork&#xff08;创建个人副本&#xff09;步骤 2: Clone&#xff08;克隆…...

当下AI智能硬件方案浅谈

背景&#xff1a; 现在大模型出来以后&#xff0c;打破了常规的机械式的对话&#xff0c;人机对话变得更聪明一点。 对话用到的技术主要是实时音视频&#xff0c;简称为RTC。下游硬件厂商一般都不会去自己开发音视频技术&#xff0c;开发自己的大模型。商用方案多见为字节、百…...