*Codeforces989D. A Shade of Moonlight
2024-08-23 20:20:03
数轴上$n \leq 100000$个不重叠的云,给坐标,长度都是$l$,有些云速度1,有些云速度-1,风速记为$w$,问在风速不大于$w_{max}$时,有几对云可能在0相遇。每一对云单独考虑。
多动一不动--相对运动。假设是原点在左右跑(当然这只是一种观点,暴力解不等式也是可以的),风速$w$时,看成原点的速度为$-w$,其他点依然像原题所述的那样飞,那么可以画出时间-坐标图象:(图片直接扒cf的)
其中蓝条表示云,橙色区域表示原点在速度不超过$w_{max}$下可能的时间-坐标轨迹的总和。可以发现,当两个云的蓝条在橙色区域有交时,就能满足题意。
由于$w_{max}>=1$,所以橙色区域的边界两条线与$x$轴是不超过45度的,而两蓝条相交区域是一个斜45度的正方形,由此起决定作用的点就是斜正方形的上顶点。把这个坐标求出来,横坐标代入橙色边界直线的函数值应该小于该点纵坐标。$u$代表向右飞的云,$v$代表向左飞的云,代入后大概是
解出来就是
把向右飞和向左飞的云的$x$分开并排序,做个二分即可。
最新文章
- 一个基于Orchard的开源CRM --coevery简介
- Nginx的第一个模块-HelloWorld
- android 之 ExpandableListView列表中的列表
- Python3基础 双星号 求一个数的几次幂
- 在Ubuntu下安装Apache
- placeholder属性兼容js支持
- Linux运维老司机:CentOS6.9配置安装并配置Rsync
- axure8.0激活
- captive portal
- Codeforces 848C Goodbye Souvenir [CDQ分治,二维数点]
- c++之&;
- 学习dart从这里开始
- js设计模式总结1
- pyqt 调用颜色选择器
- mariadb安装配置
- React 组件模式
- python 之 strip()--(转载)
- ECharts学习总结(五):echarts的Option概览
- VirtualBox 挂载共享目录
- zTree动态加载