首页 > 试题广场 >

umi和弓道

[编程题]umi和弓道

热度指数：131 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

umi对弓道非常痴迷。
有一天，她在研究一个射箭问题：
在一个无限大的平面中，她站在 $（x_{0}，y_{0}）\$ 这个坐标。
有 $n\$ 个靶子，第 $i\$ 个靶子的坐标是 $（x_{i}，y_{i}）\$
umi准备在 $x\$ 轴或 $y\$ 轴上放置一块挡板来挡住弓箭的轨迹，使得她可以射中的靶子数量不超过 $k\$ 个。
她想知道挡板的最短长度是多少？
注：假定弓箭的轨迹是起点为umi坐标、长度无穷大的射线。umi和靶子的体积可以无视。挡板的边缘碰到弓箭轨迹也可视为挡住弓箭。
注2：挡板不能弯折，起始和终点必须在同一坐标轴上。

输入描述:

第一行两个整数 ， ，代表umi的坐标。
第二行两个正整数  和  ，分别代表靶子的总数量、放置挡板后可射中靶子的最大值。
接下来的  行，每行两个整数 和 。代表每个靶子的坐标。
保证没有任何一个点在坐标轴上（无论umi还是靶子），保证没有任何两点重合。

输出描述:

若无论如何无法保证可以射中的靶子数量不超过  个，则输出  。
否则输出挡板的最小长度。如果你和正确答案的误差不超过  ，则视为答案正确。

示例1

输入

输出

0.50000000

说明

umi要保证能射中的靶子不超过0个，即全部挡住。在y轴上选区间[1,1.5]放置一个长度为0.5的挡板即可。

备注:

算法知识视频讲解

谷雨逝

发表于 2020-02-05 00:00:19

链接：https://ac.nowcoder.com/acm/contest/3002/C来源：牛客网 umi对弓道非常痴迷。有一天，她在研究一个射箭问题：在一个无限大的平面中，她站在（x0,y0) 这个坐标。有 n个靶子，第 (xi,yi) 个靶子的坐标是umi准备在 x 轴或 y 轴上放置一展开全文