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

Codeforces Round 502 E. The Supersonic Rocket 凸包、kmp

题目链接

题目大意

平面上给定两个点集,判定两个点集分别形成的凸多边形能否通过旋转、平移重合。

点集大小 ≤ \leq 1 0 5 10^{5} 105,坐标范围 [0, 1 0 8 10^{8} 108 ].

思路

题意很明显,先求出凸包再判断两凸包是否同构。这里用的 A n d r e w Andrew Andrew 算法求。判同构的话,将俩凸包都转化成字符串的形式,用 k m p kmp kmp 去匹配从而判断该串中是否存在另外一个凸包所对应的字符串。

code

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pii pair<int, int>using namespace std;
const int N = 1e5 + 100, M = 2e5 + 100;
int n, m, id;
int tmp1, tmp2, minx, ans;
pair<int, int> s[M];
pair<int, int> t[M];
int nxt[M];struct Point
{int x, y;
} tmp, st;
Point a[N];
vector<Point> v;
vector<Point> e[3];int dop(Point a, Point b)
{return a.x * b.x + a.y * b.y;
}
int crp(Point a, Point b)
{return a.x * b.y - a.y * b.x;
}
int len(Point a, Point b)
{return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
Point mins(Point a, Point b)
{Point c;c.x = b.x - a.x;c.y = b.y - a.y;return c;
}
bool cmp1(Point a, Point b)
{if (a.x == b.x){return a.y < b.y;}return a.x < b.x;
}
bool cmp(Point a, Point b)
{int sum1 = crp(mins(st, a), mins(st, b));if (sum1 == 0.0){if (a.x == b.x){return a.y < b.y;}return a.x < a.x;}return sum1 > 0.0;
}
void get_nxt()
{int i = 0, j = -1;nxt[0] = -1;while (i < 2 * e[1].size()){if (j == -1 || s[i] == s[j]){i++;j++;nxt[i] = j;}else{j = nxt[j];}}
}
bool kmp()
{int i = 0, j = 0;while (i < 2 * e[1].size()){if (j == -1 || s[i] == t[j]){i++;j++;}else if (j == e[2].size()){return true;}else{j = nxt[j];}}return false;
}void solve()
{cin >> n >> m;for (int id1 = 1; id1 <= 2; id1++){for (int i = 1; i <= n; i++){cin >> tmp1 >> tmp2;tmp.x = tmp1, tmp.y = tmp2;a[i] = tmp;}minx = 0x3f3f3f3f;sort(a + 1, a + n + 1, cmp1);st.x = a[1].x, st.y = a[1].y;id = 1;for (int i = 2; i <= n; i++){v.push_back(a[i]);}sort(v.begin(), v.end(), cmp);e[id1].push_back(a[id]);for (auto x : v){if (e[id1].size() <= 1){e[id1].push_back(x);continue;}bool fl = false;while (e[id1].size() >= 2){int sum1 = crp(mins(e[id1][e[id1].size() - 1], e[id1][e[id1].size() - 2]), mins(e[id1][e[id1].size() - 1], x));if (sum1 >= 0.0){e[id1].pop_back();}else{e[id1].push_back(x);fl = true;break;}}if (!fl){e[id1].push_back(x);}}n = m;v.clear();}if (e[1].size() != e[2].size()){cout << "NO\n";return;}for (int i = 0; i < e[1].size(); i++){s[i] = {(e[1][i].x - e[1][(i + 1) % e[1].size()].x) * (e[1][i].x - e[1][(i + 1) % e[1].size()].x) + (e[1][i].y - e[1][(i + 1) % e[1].size()].y) * (e[1][i].y - e[1][(i + 1) % e[1].size()].y), dop(mins(e[1][(i + 1) % e[1].size()], e[1][i]), mins(e[1][(i + 1) % e[1].size()], e[1][(i + 2) % e[1].size()]))};}for (int i = 0; i < e[1].size(); i++){s[i + e[1].size()] = s[i];}for (int i = 0; i < e[2].size(); i++){t[i] = {(e[2][i].x - e[2][(i + 1) % e[2].size()].x) * (e[2][i].x - e[2][(i + 1) % e[2].size()].x) + (e[2][i].y - e[2][(i + 1) % e[2].size()].y) * (e[2][i].y - e[2][(i + 1) % e[2].size()].y), dop(mins(e[2][(i + 1) % e[2].size()], e[2][i]), mins(e[2][(i + 1) % e[2].size()], e[2][(i + 2) % e[2].size()]))};}get_nxt();cout << (kmp() ? "YES" : "NO");
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int tp = 1;// cin >> t;while (tp--)solve();return 0;
}

相关文章:

Codeforces Round 502 E. The Supersonic Rocket 凸包、kmp

题目链接 题目大意 平面上给定两个点集&#xff0c;判定两个点集分别形成的凸多边形能否通过旋转、平移重合。 点集大小 ≤ \leq ≤ 1 0 5 10^{5} 105&#xff0c;坐标范围 [0, 1 0 8 10^{8} 108 ]. 思路 题意很明显&#xff0c;先求出凸包再判断两凸包是否同构。这里用…...

机器人匹诺曹机制,真话假话平衡机制

摘要&#xff1a; 本文聚焦于机器人所采用的一种“匹诺曹机制”&#xff0c;该机制旨在以大概率保持“虚拟鼻子”&#xff08;一种象征虚假程度的概念&#xff09;不会过长&#xff0c;通过在对话中夹杂真话与假话来实现。文章深入探讨了这一机制的原理&#xff0c;分析其背后的…...

用Python分割并高效处理PDF大文件

在处理大型PDF文件时&#xff0c;将它们分解成更小、更易于管理的块通常是有益的。这个过程称为分区&#xff0c;它可以提高处理效率&#xff0c;并使分析或操作文档变得更容易。在本文中&#xff0c;我们将讨论如何使用Python和为Unstructured.io库将PDF文件划分为更小的部分。…...

【RAG】混合检索(Hybrid Search) 提高检索精度

1.问题&#xff1a;向量检索也易混淆&#xff0c;而关键字会更精准 在实际生产中&#xff0c;传统的关键字检索&#xff08;稀疏表示&#xff09;与向量检索&#xff08;稠密表示&#xff09;各有利弊。 举个具体例子&#xff0c;比如文档中包含很长的专有名词&#xff0c; 关…...

CTFHub-FastCGI协议/Redis协议

将木马进行base64编码 <?php eval($_GET[cmd]);?> 打开kali虚拟机&#xff0c;使用虚拟机中Gopherus-master工具 Gopherus-master工具安装 git clone https://github.com/tarunkant/Gopherus.git 进入工具目录 cd Gopherus 使用工具 python2 "位置" --expl…...

【算法day4】最长回文子串——动态规划方法

最长回文子串 给你一个字符串 s&#xff0c;找到 s 中最长的 回文 子串。 https://leetcode.cn/problems/longest-palindromic-substring/submissions/607962358/ 动态规划&#xff1a; 回文串即是从前面开始读和从后面开始读&#xff0c;读出来的字符串均相同的字符串&#…...

C++之“string”类的模拟实现

​ &#x1f339;个人主页&#x1f339;&#xff1a;喜欢草莓熊的bear &#x1f339;专栏&#x1f339;&#xff1a;C入门 前言 hello &#xff0c;大家又来跟着bear学习了。一起奔向更好的自己&#xff0c;上篇博客已经讲清楚了string的一些功能的使用。我们就实现一些主要的功…...

请谈谈 HTTP 中的安全策略,如何防范常见的Web攻击(如XSS、CSRF)?

一、Web安全核心防御机制 &#xff08;一&#xff09;XSS攻击防御&#xff08;跨站脚本攻击&#xff09; 1. 原理与分类 ​存储型XSS&#xff1a;恶意脚本被持久化存储在服务端&#xff08;如数据库&#xff09;​反射型XSS&#xff1a;脚本通过URL参数或表单提交触发执行​…...

Python Flask 渲染静态程动态页面

Python Flask 渲染静态程动态页面 Python Flask 渲染静态程动态页面 Python Flask 渲染静态程动态页面 对网页应用程序来说&#xff0c;静态内容是重要的&#xff0c;因为它们包括 CSS 和 JavaScript 文件。静态文件可以直接由网页服务器提供。如果我们在我们的项目中创建一个…...

Unity大型游戏开发全流程指南

一、开发流程与核心步骤 1. 项目规划与设计阶段 需求分析 明确游戏类型&#xff08;MMORPG/开放世界/竞技等&#xff09;、核心玩法&#xff08;战斗/建造/社交&#xff09;、目标平台&#xff08;PC/移动/主机&#xff09;示例&#xff1a;MMORPG需规划角色成长树、副本Boss…...

Unity场景制作

一、关于后处理效果 然后可在后处理组件中添加各种效果 ACES : 电影感的强对比效果 添加了ACES后场景明显变暗&#xff0c;所以可以提高曝光度 Post-exposure 二、添加雾效 在Window的项目栏中选择Render中的Lighting 在环境属性中的其他设置中可勾选雾效&#xff0c;为场景中添…...

PCIE接口

PCIE接口 PIC接口介绍PIC总线结构PCI总线特点PCI总线的主要性能PIC的历程 PCIE接口介绍PCIe接口总线位宽PCIE速率GT/s和Gbps区别PCIE带宽计算 PCIE架构PCIe体系结构端到端的差分数据传递PCIe总线的层次结构事务层数据链路层物理层PCIe层级结构及功能框图 PCIe链路初始化PCIe链路…...

Leetcode 3479. Fruits Into Baskets III

Leetcode 3479. Fruits Into Baskets III 1. 解题思路2. 代码实现 题目链接&#xff1a;3479. Fruits Into Baskets III 1. 解题思路 这一题思路本质上就是考察每一个水果被考察时找到第一个满足条件且未被使用的basket。 因此&#xff0c;我们只需要将basket按照其capacit…...

小程序 -- uni-app开发微信小程序环境搭建(HBuilder X+微信开发者工具)

目录 前言 一 软件部分 1. 微信开发者工具 2. HBuilder X 开发工具 二 配置部分 1. 关于 HBuilder X 配置 2. 关于 微信开发工具 配置 三 运行项目 1. 新建项目 2. 代码编写 3. 内置浏览器 编译 4. 配置小程序 AppID获取 注意 四 实现效果 前言 uni-app开发小程…...

深度学习PyTorch之13种模型精度评估公式及调用方法

深度学习pytorch之22种损失函数数学公式和代码定义 深度学习pytorch之19种优化算法&#xff08;optimizer&#xff09;解析 深度学习pytorch之4种归一化方法&#xff08;Normalization&#xff09;原理公式解析和参数使用 深度学习pytorch之简单方法自定义9类卷积即插即用 实时…...

《云原生监控体系构建实录:从Prometheus到Grafana的观测革命》

PrometheusGrafana部署配置 Prometheus安装 下载Prometheus服务端 Download | PrometheusAn open-source monitoring system with a dimensional data model, flexible query language, efficient time series database and modern alerting approach.https://prometheus.io/…...

GHCTF2025--Web

upload?SSTI! import os import refrom flask import Flask, request, jsonify,render_template_string,send_from_directory, abort,redirect from werkzeug.utils import secure_filename import os from werkzeug.utils import secure_filenameapp Flask(__name__)# 配置…...

NO.32十六届蓝桥杯备战|函数|库函数|自定义函数|实参|形参|传参(C++)

函数是什么 数学中我们其实就⻅过函数的概念&#xff0c;⽐如&#xff1a;⼀次函数 y kx b &#xff0c;k和b都是常数&#xff0c;给⼀个任意的x &#xff0c;就得到⼀个 y 值。其实在C/C语⾔中就引⼊了函数&#xff08;function&#xff09;的概念&#xff0c;有些翻译为&a…...

计算机视觉算法实战——老虎个体识别(主页有源码)

✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连✨ ​ ​​​ 1. 领域介绍 老虎个体识别是计算机视觉中的一个重要应用领域&#xff0c;旨在通过分析老虎的独特条纹图案&#xff0c;自动识别和区…...

【移动WEB开发】rem适配布局

目录 1. rem基础 2.媒体查询 2.1 语法规范 2.2 媒体查询rem 2.3 引入资源&#xff08;理解&#xff09; 3. less基础 3.1 维护css的弊端 3.2 less介绍 3.3 less变量 3.4 less编译 3.5 less嵌套 3.6 less运算 4. rem适配方案 4.1 rem实际开发 4.2 技术使用 4.3 …...

OpenClaw故障排查大全:百川2-13B量化模型接入常见报错解决

OpenClaw故障排查大全&#xff1a;百川2-13B量化模型接入常见报错解决 1. 当网关拒绝启动时 上周深夜调试OpenClaw时&#xff0c;我遇到了最棘手的网关启动失败问题。控制台反复报错Error: listen EADDRINUSE: address already in use :::18789&#xff0c;但用lsof -i :1878…...

ROS2 Jazzy尝鲜指南:在Ubuntu 24.04上从安装到跑通第一个Demo(附常见错误修复)

ROS2 Jazzy尝鲜指南&#xff1a;在Ubuntu 24.04上从安装到跑通第一个Demo Ubuntu 24.04 LTS的发布带来了全新的ROS2 Jazzy版本&#xff0c;这对机器人开发者来说无疑是一次令人兴奋的技术升级。作为长期支持版本&#xff0c;Jazzy将在未来五年内获得官方维护&#xff0c;这意味…...

ViGEmBus虚拟手柄驱动全栈技术指南:从内核原理到游戏控制革新

ViGEmBus虚拟手柄驱动全栈技术指南&#xff1a;从内核原理到游戏控制革新 【免费下载链接】ViGEmBus Windows kernel-mode driver emulating well-known USB game controllers. 项目地址: https://gitcode.com/gh_mirrors/vi/ViGEmBus 一、认知虚拟手柄技术&#xff1a;…...

PowerShell效率提升秘籍:10个必备插件让你的终端飞起来

PowerShell效率革命&#xff1a;10款生产力插件深度评测与实战指南 对于每天与终端打交道的开发者来说&#xff0c;PowerShell的默认功能往往难以满足高效开发的需求。本文将深入剖析10款经过实战检验的效率工具&#xff0c;从智能补全到目录导航&#xff0c;从文件操作到命令解…...

基于LSTM的短期电力负荷预测研究

【负荷预测】基于LSTM短期负荷预测&#xff0c;可考虑需求响应 短期电力负荷预测在电力系统的调度、生产和规划中起着重要的作用&#xff0c;精准的负荷预测有利于决策者做出正确决策计划以及有利于电力系统的稳定运行。 多个售电主体的市场竞争带来了电价的波动&#xff0c;以…...

首款支持AI渗透的WebShell管理工具,聊个天就能实现免杀|实现高隐蔽内网渗透

0x01 工具介绍 金刚狼首款支持 AI 渗透的 WebShell MCP&#xff0c;也是一款支持多层内网级联的 ASPX、ASHX 高级 WebShell 管理工具。工具采用 AES 加密通信&#xff0c;无需代理即可实现内网穿透&#xff0c;支持内存加载各类渗透工具&#xff0c;做到无文件落地隐蔽渗透目标…...

OpenClaw快速安装部署:让AI住进你的电脑

一、前言 上篇说完OpenClaw是什么&#xff0c;有小伙伴留言说&#xff1a;“听起来挺猛&#xff0c;但安装肯定很复杂吧&#xff1f;”确实&#xff0c;之前我也有这个顾虑。毕竟涉及到Gateway、Agent、多渠道配置&#xff0c;听起来就头大。 但实际搞下来——就两条命令。 今天…...

Quartus-II 9.0实战:从半加器到4位加法器的数字逻辑设计全流程解析

1. 半加器设计&#xff1a;数字逻辑的起点 半加器是数字电路设计中最基础的加法单元&#xff0c;理解它的工作原理对后续学习全加器和多位加法器至关重要。半加器之所以称为"半"&#xff0c;是因为它只能处理两个1位二进制数的相加&#xff0c;不考虑来自低位的进位输…...

2026降AI率工具红黑榜:降AI率工具怎么选?一篇讲透

千笔AI、ThouPen、豆包是当前适配国内高校AI率检测规范的优质选择&#xff1b;需警惕低质免费工具、无正规检测对接、改写痕迹生硬的平台&#xff1b;建议按降AI效果、学术合规性、使用成本三维度筛选&#xff0c;优先匹配A-B-C模型。 一、红榜&#xff1a;10 款高分论文降AI率…...

ArcGIS Desktop许可证被占满?别慌,这3个方法帮你快速释放Advanced许可(附详细步骤)

ArcGIS Desktop高级许可被占用&#xff1f;3种高效解决方案与实战技巧 当你正在赶制项目报告或处理关键地理数据时&#xff0c;突然弹出的"All ArcGIS for Desktop Advanced licenses are in use"错误提示足以让任何GIS专业人士心跳加速。这种情况往往发生在团队共享…...