题目背景

SPJ题目

题目描述

本题给出平面上 $n$ 个点的坐标，第 $i$ 个点的坐标是 $(x_i, y_i)$。定义两点的斜率为：$\frac{y_i - y_j}{x_i - x_j}$，也就是纵坐标之差除以横坐标之差。本题保证这 $n$ 个点的横坐标各不相同。

你的任务是：从这 $n$ 个点中选出恰好 $k$ 个点，使得最大化这 $k$ 个点两两之间的斜率的最小值。也就是说，你需要求出如下的式子的值：

$\max\limits_{|S| = k} \left\{ \min\limits_{i, j \in S, i \ne j} \frac{y_i - y_j}{x_i - x_j} \right\}$

其中 $S$ 表示你选择的点的集合，$|S|$ 表示集合内元素个数。

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每一组数据，第一行两个正整数 $n,k$，分别表示总点数和你需要选择的点数。接下来 $n$ 行，每行输入两个数 $x_i, y_i$，表示这个点的坐标。

输出格式

对于每一组数据，输出一行一个实数，表示答案。

• 请保留六位小数

你的答案与标准答案之间的相对误差或绝对误差不超过 $10^{-6}$ 时视为答案正确。(注意!!! 目前由于未使用special judge, 可能答案正确但是未得到满分，请尽量精确，然后使用标准的保留小数方式)

spj written by meyi.

输入样例

2
4 3
1 2
2 4
3 3
4 1
2 2
1 1
5 3

输出样例

-1.000000
0.500000

说明提示

样例解释

第一组样例，如下图所示，红色的为选择的点：

• 对于 30% 的数据，$2 \le k \le n \le 10$，保证单个测试点 $\sum n \le 10$。

• 对于 60% 的数据，$2 \le k \le n \le 1000$，保证单个测试点 $\sum n \le 1000$。

• 对于 100% 的数据，$1 \le T \le 100, 2\le k \le n \le 10^5, 0 \le x_i, y_i \le 10^9$。保证单个测试点 $\sum n \le 10^5$。

保证所有点的横坐标各不相同。

本站补充：原套别：第 12 套 B 题。

本站补充：样例图勘误：图中红色 B、C、D 的最小斜率为 -2；样例答案 -1 对应选择 A、B、C。原图保留供核对。