Opentrains 1519 G——最小圆覆盖
2024-09-02 17:25:57
题目
给出 $n$ 个定义在区间 $[0, 1]$ 上的一次函数 $f_i(x) = a_ix+b_i$,定义两个函数的距离为:
$$dist(f,g) = \left(\max_{0\leq i\leq T} (f(i)-g(i))\right)^2 + \left(\min_{0\leq i\leq T}(f(i)-g(i))\right)^2$$
你现在要找一个一次函数 $g(x) = cx+d$,使得下面的值最小:
$$\max_{1\leq i\leq n} dist(f_i, g)$$
你只需要输出最小值就可以了。($1\leq n \leq 200000$)
分析
一次函数减一次函数仍是一次函数,所以最值在端点取得。(画图也能发现)
即 $dust(f, g) = \left(f(0)-g(0) \right)^2 + \left(f(T) - g(T) \right)^2$
这是很熟悉的点到点的距离公式,如果我们把 $\left(f(0), f(T) \right)$,共有 $n$ 个点,$dist(f_i, g)$ 即为 $\left(g(0), g(T) \right)$ 到第 $i$ 个点的距离。
要求的就是到 $n$ 个点的最大距离的最小值,转化为求最小圆覆盖中的圆的半径。
参考链接: https://yang2002.github.io/2019/04/21/最小圆覆盖学习笔记/
最新文章
- python 学习(json)(转)
- Android自定义实现FlowLayout
- 转载 yii2-按需加载并管理CSS样式/JS脚本
- CCPC网络赛,HDU_5842 Lweb and String
- 模拟dispatch_once
- Linux内核中常见内存分配函数(三)
- Spring 之 示例(Java之负基础实战)
- flume 1.7在windows下的安装与测试
- 如何在已有的 Web 应用中使用 ReactJS
- pillow的用法
- django补充
- Always run a program in administrator mode in Windows 10
- Java日期时间,以及相互转换
- Runnable接口和Callable接口的区别。
- Maven让资源文件处理插件能够解析资源文件中的Maven属性
- Android TextView文字透明度和背景透明度设置
- react native组件的创建
- php面向对象编程_2
- 题解【luogu4145 上帝造题的七分钟2(花神游历各国)】
- 自己写着玩的一个天气APP