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

CF333E Summer Earnings

推歌:Between Worlds

很有意思的题。

注意到题目其实就是选三个点使得两两之间欧几里得距离最小值最大,很容易就有 \(O(n^3)\) 做法。

常规方法是注意到本题时限极大,而最小值最大又是可以从大到小枚举最小值的,因此把所有的点对按照距离排序从大到小扫,每次就是对 \((i,j)\) 求是否有 \(k\) 使得 \((i,k)\)\((k,j)\) 的距离都比它大,可以很容易地用 Bitset 维护,\(O(\frac{n^3}{\omega})\) 即可通过。

但是有没有不靠 \(\omega\) 的方法呢?让我们使用一些中学学过的数学知识。

初中有一句话叫做“大角对大边”(其实就是正弦定理)而题目的问题又等价于求三角形中最短边的最大值,所以直接考虑枚举一个点 \(P\) 作为顶点。我们发现三角形的最小角一定是 \(\le \frac{\pi}{3}\) 的,如果以 \(P\) 为顶点的 \(\angle APB\ge \frac{\pi}{3}\),那么此三角形的最短边一定在 \(PA\)\(PB\) 中。

因此固定 \(A\) 后,我们要找的 \(B\) 就是使得 \(\angle APB\ge \frac{\pi}{3}\)\(PB\) 最短的点,这是一个静态区间最小值!

然后我们就可以直接做了。枚举 \(P\),将剩余的点以 \(P\) 为原点进行极角排序,ST 表预处理区间最小值,枚举 \(A\) 并快速求 \(B\)。由于每个点都会作为顶点出现所以不会有哪组最短边没扫到的情况。时间复杂度 \(O(n^2\log n)\)

感觉其实并不算数学题?只是用了基础的几何知识而已。

http://www.hskmm.com/?act=detail&tid=15572

相关文章:

  • 一文看懂Playwright MCP如何引爆AI智能体爆发
  • 从nano banana模型到更加真实的3D打印技术
  • 职业卡点怎么破?3个月私教服务助你升级技能与面试技巧
  • OI?原来这么简单-语法算法入门篇
  • 跨境tk避雷proxy-cheap代理服务商!!!
  • Rouyan:使用WPF/C#构建的基于LLM的快捷翻译小工具
  • BM25 关键词检索算法
  • 记录用户业务请求日志
  • [C++:类的默认成员函数——Lesson7.const成员函数] - 指南
  • 详细介绍:Xilinx系列FPGA实现12G-SDI音视频编解码,支持4K60帧分辨率,提供2套工程源码和技术支持
  • 使用 VMware Workstation 安装 CentOS-7 虚拟机
  • K12教育 和 STEAM教育
  • AT_arc167_c [ARC167C] MST on Line++
  • Lombok无法使用get set方法
  • redis的哈希扩容
  • vite tailwindcss配置
  • 在Vona ORM中实现多数据库/多数据源
  • 实用指南:python全栈-数据可视化
  • sql over()函数使用
  • Git回退版本 reset、revert、read-tree、restore
  • Avalonia 背景颜色Transparent在用户界面设计中对悬浮效果影响的总结
  • 飞书 燕千云焕新上线,飞书用户即刻试用ITSM工具
  • 如果使用微软 Azure 托管的 OpenAI 服务
  • Python类
  • 什么是文件外发审批?主要有哪几种关键流程?
  • VPX处理板设计原理图:9-基于DSP TMS320C6678+FPGA XC7V690T的6U VPX信号处理卡 C6678板卡, XC7VX690T板卡, VPX处理板
  • VitePress 添加友链界面
  • 跨网文件摆渡软件:企业数据安全高效传输的关键解决方案!
  • 洛谷题单指南-进阶数论-P1495 【模板】中国剩余定理(CRT)/ 曹冲养猪
  • 第十四届蓝桥杯青少组C++选拔赛[2022.12.18]第二部分编程题(4、充电站) - 指南