【线段树二分】第十三届蓝桥杯省赛C++ A组/研究生组 Python 研究生组《扫描游戏》(C++)

【题目描述】

有一根围绕原点 O 顺时针旋转的棒 OA,初始时指向正上方(Y 轴正向)。

在平面中有若干物件,第 i 个物件的坐标为(x_{i},y_{i}),价值为 z_{i}

当棒扫到某个物件时,棒的长度会瞬间增长 z_{i},且物件瞬间消失(棒的顶端恰好碰到物件也视为扫到),如果此时增长完的棒又额外碰到了其他物件,也按上述方式消去(它和上述那个点视为同时消失)。

如果将物件按照消失的时间排序,则每个物件有一个排名,同时消失的物件排名相同,请输出每个物件的排名,如果物件永远不会消失则输出 −1。

所有物品坐标两两不同。

【输入格式】

输入第一行包含两个整数 n、L,用一个空格分隔,分别表示物件数量和棒的初始长度。

接下来 n 行每行包含第三个整数x_{i},y_{i}z_{i}

【输出格式】

输出一行包含 n 整数,相邻两个整数间用一个空格分隔,依次表示每个物件的排名。

【数据范围】

对于 30% 的评测用例,1≤n≤500;
对于 60% 的评测用例,1≤n≤5000;
对于所有评测用例,1≤n≤200000,−10^{9} ≤ x_{i},y_{i} ≤ 10^{9},1 ≤ L,z_{i} ≤ 10^{9}

【输入样例】

5 2
0 1 1
0 3 2
4 3 5
6 8 1
-51 -33 2

【输出样例】

1 1 3 4 -1

【思路】

题解来源:AcWing 4649. 扫描游戏 - AcWing

【代码】

#include <bits/stdc++.h>
typedef long long LL;
const int N = 2e5 + 10;
const __int128 INF = 1e38;
int n, ans[N], idx;
__int128 len;template <typename T> //快读模板
inline T fastread(T &x)
{x = 0;T w = 1;char ch = 0;while (ch < '0' || ch > '9'){if (ch == '-')w = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + (ch - '0');ch = getchar();}return x = x * w;
}struct point
{LL x, y, z;int id;
} a[N];
int Quadrant(point a) //因为棒是顺时针旋转,我们这里把正常意义下的二四象限调换一下
{if (a.x >= 0 && a.y > 0)return 1;if (a.x > 0 && a.y <= 0)return 2;if (a.x <= 0 && a.y < 0)return 3;elsereturn 4;
}
LL cross(point a, point b) //求叉积
{return a.x * b.y - a.y * b.x;
}
bool cmp(point a, point b) //极角排序,排序完后,所有点就按顺时针排好了
{if (Quadrant(a) == Quadrant(b)){if (cross(a, b) == 0) //当极角相同,我们这里按照距离原点距离的平方来排序return a.x * a.x + a.y * a.y < b.x * b.x + b.y * b.y;return cross(a, b) < 0;}return Quadrant(a) < Quadrant(b);
}//线段树
struct
{__int128 minv;
} seg[N * 4]; //线段树维护的是点到原点的距离的区间最小值
void pushup(int id)
{seg[id].minv = std::min(seg[id << 1].minv, seg[id << 1 | 1].minv);
}
void build(int id, int l, int r)
{if (l == r)seg[id].minv = a[l].x * a[l].x + a[l].y * a[l].y;else{int mid = l + r >> 1;build(id << 1, l, mid);build(id << 1 | 1, mid + 1, r);pushup(id);}
}
void change(int id, int l, int r, int pos, __int128 val)
{if (l == r)seg[id].minv = val;else{int mid = l + r >> 1;if (pos <= mid)change(id << 1, l, mid, pos, val);elsechange(id << 1 | 1, mid + 1, r, pos, val);pushup(id);}
}
int search(int id, int l, int r, int ql, int qr, __int128 val) //线段树上二分模板
//返回[ql,qr]这段区间里从左至右第一个小于等于val的元素的下标,不存在就返回-1
{if (l == ql && r == qr) //此时的区间正好是询问区间{if (seg[id].minv > val) //如果整个区间的最小值都大于val,直接返回-1return -1;else{if (l == r)return l;int mid = l + r >> 1;if (seg[id << 1].minv <= val) //如果左儿子里有这样的元素,直接进入左儿子即可return search(id << 1, l, mid, ql, mid, val);else //否则进入右儿子return search(id << 1 | 1, mid + 1, r, mid + 1, qr, val);}return seg[id].minv;}int mid = l + r >> 1;if (qr <= mid)return search(id << 1, l, mid, ql, qr, val);else if (ql > mid)return search(id << 1 | 1, mid + 1, r, ql, qr, val);else{int pos = search(id << 1, l, mid, ql, mid, val);if (pos == -1)return search(id << 1 | 1, mid + 1, r, mid + 1, qr, val);elsereturn pos;}
}
signed main()
{// 注意用了快读就不能关闭流同步,不然大概率会炸fastread(n), fastread(len);for (int i = 1; i <= n; ++i) //初始化ans数组ans[i] = -1;for (int i = 1; i <= n; ++i){fastread(a[i].x), fastread(a[i].y), fastread(a[i].z);a[i].id = i;}std::sort(a + 1, a + n + 1, cmp);build(1, 1, n);int last = 0;     // last维护上一个扫到的点int rank = 0;     // rank记录扫到点的排名int lastrank = 0; // 维护lastrank主要是为了处理有几个点极角相同的特殊情况,根据题意它们的排名相同while (true){int idx = -1;if (last + 1 <= n) //一定要记得这句ifidx = search(1, 1, n, last + 1, n, len * len);if (idx != -1)len += a[idx].z;else{if (last >= 2) //一定要记得这句ifidx = search(1, 1, n, 1, last - 1, len * len);if (idx != -1)len += a[idx].z;}if (idx == -1) //没能找到可以划到的点,退出死循环break;change(1, 1, n, idx, INF); //对于扫过的点,我们可以把它单点修改成无穷大,等价于它消失了if (last == 0)ans[a[idx].id] = ++rank, lastrank = rank;else{if (Quadrant(a[last]) == Quadrant(a[idx]) && cross(a[last], a[idx]) == 0) //该点和上一个点是同时被扫到的,所以排名要一样ans[a[idx].id] = lastrank, ++rank;elseans[a[idx].id] = ++rank, lastrank = rank;}last = idx;}for (int i = 1; i <= n; ++i)printf("%d ", ans[i]);printf("\n");return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/287842.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

R语言ggplot2 | 热图+随机森林重要性!升级版~

&#x1f4cb;文章目录 原图复现定义ggrf_ggcor_plot()函数加载数据集一键出图函数优点 今天推出一个升级版&#xff1a; ggrf_ggcor_plot的函数。只需要输入 响应变量的矩阵和 解释变量的矩阵&#xff0c;就能轻松一键生成随机森林重要性相关性热图。 原图 所需复现的随机森…

发车,易安联签约某新能源汽车领军品牌,为科技创新保驾护航

近日&#xff0c;易安联成功签约某新能源汽车领军品牌&#xff0c;为其 数十万终端用户 建立一个全新的 安全、便捷、高效一体化的零信任终端安全办公平台。 随着新能源汽车行业的高速发展&#xff0c;战略布局的不断扩大&#xff0c;技术创新不断引领其市场价值走向高点&am…

如何在数字化转型中确保数据安全

随着科技的飞速发展&#xff0c;数字化转型已成为企业发展的必然趋势。数字化转型是指企业利用数字技术对业务流程、组织结构和商业模式进行全面创新和变革&#xff0c;以提高企业的竞争力和创新能力。然而&#xff0c;在数字化转型过程中&#xff0c;数据安全问题日益凸显&…

新能源汽车充电桩主板各模块成本占比解析

汽车充电桩主板是汽车充电桩的重要组件&#xff0c;主要由微处理器模块、通信模块、控制模块、安全保护模块、传感器模块等多个模块构成。深入探究各模块在总成本中的比重&#xff0c;我们可以更好地优化成本结构、提高生产效率&#xff0c;并为未来的技术创新和市场需求变化做…

R语言学习——Rstudio软件

R语言免费但有点难上手&#xff0c;是数据挖掘的入门级别语言&#xff0c;拥有顶级的可视化功能。 优点&#xff1a; 1统计分析&#xff08;可以实现各种分析方法&#xff09;和计算&#xff08;有很多函数&#xff09; 2强大的绘图功能 3扩展包多&#xff0c;适合领域多 …

Docker - 哲学 默认网络和 自定义网络 与 linux 网络类型 和 overlay2

默认网络&#xff1a;不指定 --nerwork 不指定 网络 run 一个容器时&#xff0c;会直接使用默认的网络桥接器 &#xff08;docker0&#xff09; 自定义网络&#xff1a;指定 --nerwork 让这两台容器互相通信 的前提 - 共享同一个网络 关于 ip addr 显示 ens160 储存驱动 ov…

入行AI写作第一个月收入2万+复盘分享

入行AI写作第一个月收入2万复盘分享 AI写作作为一种新兴的创作方式&#xff0c;正逐渐改变着内容产业的生态。在这个领域中&#xff0c;许多人通过自己的努力和智慧&#xff0c;实现了快速的成长和收入的增长。本文将从技术学习与掌握、实践与应用、内容创作与优化、持续学习与…

java 面向对象入门

类的创建 右键点击对应的包&#xff0c;点击新建选择java类 填写名称一般是名词&#xff0c;要知道大概是什么的名称&#xff0c;首字母一般大写 下面是创建了一个Goods类&#xff0c;里面的成员变量有&#xff1a;1.编号&#xff08;id&#xff09;&#xff0c;2.名称&#x…

护眼落地灯怎么选?五款好评连连的护眼大路灯曝光!

现代人越来越重视视力健康&#xff0c;而护眼落地灯则可以很好的提供良好的光线来帮助大家解决平时用眼时的不良光线困扰&#xff0c;因此&#xff0c;受到了很多人喜爱。但是&#xff0c;在产品爆火的同时&#xff0c;市场上也出现了一些质量差且劣质的护眼落地灯&#xff0c;…

Microsoft .NET 应用程序性能监控

什么是 .NET监控 Microsoft .NET 监视在确保可以开发和部署应用程序而不必面对性能滞后或中断方面发挥着重要作用。它使用警报、增长趋势报告和数据可视化技术来帮助管理员确保 Microsoft .NET 平台的全天候可用性。Microsoft.NET 性能监视是一种检测性能异常的先发制人方法&a…

linux 网卡配置 vlan/bond/bridge/macvlan/ipvlan 模式

linux 网卡模式 linux网卡支持非vlan模式、vlan模式、bond模式、bridge模式&#xff0c;macvlan模式、ipvlan模式等&#xff0c;下面介绍交换机端及服务器端配置示例。 前置要求&#xff1a; 准备一台物理交换机&#xff0c;以 H3C S5130 三层交换机为例准备一台物理服务器&…

Nacos配置中心的敏感数据加密处理

为了简化运维工作,使用nacos作为配置中心,但很多敏感数据都是明文存储的,这样一旦数据泄露,可能会造成很大影响,所以最好把这些数据进行加密处理,下面介绍几种数据的加密。 一、数据库信息加密 数据库的配置本篇介绍两种,一是使用druid连接池的,这种比较常见;二是使…

网络安全-提权篇

我们在文件包含的时候可以将错误的用户名包含进日志&#xff0c;但是权限问题让人很烦恼&#xff0c;今天的侧重点主要是跟大家聊一聊提权 用户名包含进日志参考&#xff1a;RCE with LFI and SSH Log Poisoning - Hacking Articles 目录 一、环境 二、看看权限&#xff08;…

vue指令相关

vue中有很多的指令像v-on、v-model、v-bind等是我们开发中常用的 常用指令 v-bind 单向绑定解析表达式 v-model 双向数据绑定 v-for 遍历数组/对象/字符串 v-on 绑定事件监听,可简写为@ v-show 条件渲染(动态控制节点是否存展示) v-if 条件渲染(动态控制节点是否存存在) v…

AI智聊功能支持生成旅游攻略、作文、标题优化,方便视频剪辑

在快节奏的生活中&#xff0c;我们总是需要快速、准确地获取所需信息。无论是撰写旅游攻略、作文&#xff0c;还是准备演讲稿&#xff0c;AI智聊都能为您一键生成精彩文案&#xff0c;让您的创意无限发挥&#xff01; 媒体梦工厂的AI智聊功能&#xff0c;利用先进的自然语言处…

Teamcenter 快速获取所有激活状态用户的方法

问题描述&#xff1a; License数量有限&#xff0c;需要分析Teamcenter 中所有激活状态下的用户&#xff0c;对其进行删减。如何快速获取Teamcenter 中所有激活状态用户呢&#xff1f; 解决方法&#xff1a; Teamcenter Query Builder提供了强大的自定义搜索功能。 新建查询…

软考高级架构师:云原生架构模式概念和例题

作者&#xff1a;明明如月学长&#xff0c; CSDN 博客专家&#xff0c;大厂高级 Java 工程师&#xff0c;《性能优化方法论》作者、《解锁大厂思维&#xff1a;剖析《阿里巴巴Java开发手册》》、《再学经典&#xff1a;《Effective Java》独家解析》专栏作者。 热门文章推荐&am…

v4l2采集视频

Video4Linux2&#xff08;v4l2&#xff09;是用于Linux系统的视频设备驱动框架&#xff0c;它允许用户空间应用程序直接与视频设备&#xff08;如摄像头、视频采集卡等&#xff09;进行交互。 linux系统下一切皆文件&#xff0c;对视频设备的操作就像对文件的操作一样&#xff…

TinyEMU源码分析之启动流程

TinyEMU源码分析之启动流程 1 始于0x10002 确定BBL入口点3 mentry.S执行过程4 启动流程小结 本文属于《 TinyEMU模拟器基础系列教程》之一&#xff0c;欢迎查看其它文章。 本文中使用的代码&#xff0c;均为伪代码&#xff0c;删除了部分源码。 1 始于0x1000 我们沿着TinyEMU…

Java 学习和实践笔记(48):怎样用二维数组来存储表格数据?

怎样用数组的方式&#xff0c;来存储下面这个表格的数据&#xff1f; 示例代码如下&#xff1a; import java.util.Arrays;public class Test001 {public static void main(String[] args) {/*object类对象是类层次结构的根。每个类都有Object作为超类。所有对象&#xff0c;包…