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
题目链接 题目大意 平面上给定两个点集,判定两个点集分别形成的凸多边形能否通过旋转、平移重合。 点集大小 ≤ \leq ≤ 1 0 5 10^{5} 105,坐标范围 [0, 1 0 8 10^{8} 108 ]. 思路 题意很明显,先求出凸包再判断两凸包是否同构。这里用…...
机器人匹诺曹机制,真话假话平衡机制
摘要: 本文聚焦于机器人所采用的一种“匹诺曹机制”,该机制旨在以大概率保持“虚拟鼻子”(一种象征虚假程度的概念)不会过长,通过在对话中夹杂真话与假话来实现。文章深入探讨了这一机制的原理,分析其背后的…...
用Python分割并高效处理PDF大文件
在处理大型PDF文件时,将它们分解成更小、更易于管理的块通常是有益的。这个过程称为分区,它可以提高处理效率,并使分析或操作文档变得更容易。在本文中,我们将讨论如何使用Python和为Unstructured.io库将PDF文件划分为更小的部分。…...
【RAG】混合检索(Hybrid Search) 提高检索精度
1.问题:向量检索也易混淆,而关键字会更精准 在实际生产中,传统的关键字检索(稀疏表示)与向量检索(稠密表示)各有利弊。 举个具体例子,比如文档中包含很长的专有名词, 关…...
CTFHub-FastCGI协议/Redis协议
将木马进行base64编码 <?php eval($_GET[cmd]);?> 打开kali虚拟机,使用虚拟机中Gopherus-master工具 Gopherus-master工具安装 git clone https://github.com/tarunkant/Gopherus.git 进入工具目录 cd Gopherus 使用工具 python2 "位置" --expl…...
【算法day4】最长回文子串——动态规划方法
最长回文子串 给你一个字符串 s,找到 s 中最长的 回文 子串。 https://leetcode.cn/problems/longest-palindromic-substring/submissions/607962358/ 动态规划: 回文串即是从前面开始读和从后面开始读,读出来的字符串均相同的字符串&#…...
C++之“string”类的模拟实现
🌹个人主页🌹:喜欢草莓熊的bear 🌹专栏🌹:C入门 前言 hello ,大家又来跟着bear学习了。一起奔向更好的自己,上篇博客已经讲清楚了string的一些功能的使用。我们就实现一些主要的功…...
请谈谈 HTTP 中的安全策略,如何防范常见的Web攻击(如XSS、CSRF)?
一、Web安全核心防御机制 (一)XSS攻击防御(跨站脚本攻击) 1. 原理与分类 存储型XSS:恶意脚本被持久化存储在服务端(如数据库)反射型XSS:脚本通过URL参数或表单提交触发执行…...
Python Flask 渲染静态程动态页面
Python Flask 渲染静态程动态页面 Python Flask 渲染静态程动态页面 Python Flask 渲染静态程动态页面 对网页应用程序来说,静态内容是重要的,因为它们包括 CSS 和 JavaScript 文件。静态文件可以直接由网页服务器提供。如果我们在我们的项目中创建一个…...
Unity大型游戏开发全流程指南
一、开发流程与核心步骤 1. 项目规划与设计阶段 需求分析 明确游戏类型(MMORPG/开放世界/竞技等)、核心玩法(战斗/建造/社交)、目标平台(PC/移动/主机)示例:MMORPG需规划角色成长树、副本Boss…...
Unity场景制作
一、关于后处理效果 然后可在后处理组件中添加各种效果 ACES : 电影感的强对比效果 添加了ACES后场景明显变暗,所以可以提高曝光度 Post-exposure 二、添加雾效 在Window的项目栏中选择Render中的Lighting 在环境属性中的其他设置中可勾选雾效,为场景中添…...
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. 代码实现 题目链接:3479. Fruits Into Baskets III 1. 解题思路 这一题思路本质上就是考察每一个水果被考察时找到第一个满足条件且未被使用的basket。 因此,我们只需要将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种优化算法(optimizer)解析 深度学习pytorch之4种归一化方法(Normalization)原理公式解析和参数使用 深度学习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++)
函数是什么 数学中我们其实就⻅过函数的概念,⽐如:⼀次函数 y kx b ,k和b都是常数,给⼀个任意的x ,就得到⼀个 y 值。其实在C/C语⾔中就引⼊了函数(function)的概念,有些翻译为&a…...
计算机视觉算法实战——老虎个体识别(主页有源码)
✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连✨ 1. 领域介绍 老虎个体识别是计算机视觉中的一个重要应用领域,旨在通过分析老虎的独特条纹图案,自动识别和区…...
【移动WEB开发】rem适配布局
目录 1. rem基础 2.媒体查询 2.1 语法规范 2.2 媒体查询rem 2.3 引入资源(理解) 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 …...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?
在工业自动化持续演进的今天,通信网络的角色正变得愈发关键。 2025年6月6日,为期三天的华南国际工业博览会在深圳国际会展中心(宝安)圆满落幕。作为国内工业通信领域的技术型企业,光路科技(Fiberroad&…...
【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础
第三周 Day 3 🎯 今日目标 理解类(class)和对象(object)的关系学会定义类的属性、方法和构造函数(init)掌握对象的创建与使用初识封装、继承和多态的基本概念(预告) &a…...
