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 …...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
