#P8940. [2020年省队模拟]文学

    ID: 9033 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 6 上传者: 标签>动态规划计算几何字符串贪心CF2100二分模拟构造

[2020年省队模拟]文学

文学

题目描述

给定 NN 个二元组 S={(a1,b1),…,(aN,bN)}S=\{(a_1,b_1),\ldots,(a_N,b_N)\},定义

f(S,A,B)=max⁡(ai,bi)∈S(Aai+Bbi).f(S,A,B)=\max_{(a_i,b_i)\in S}(Aa_i+Bb_i).

选出恰好 RR 个二元组组成 T⊆ST\subseteq S,使

$$\inf_{A,B\in\mathbb Z_{>0}}\frac{f(T,A,B)}{f(S,A,B)}$$

最大。这里 A,BA,B 均为正整数,所求是下确界,包括只能通过比值趋于边界而逼近的值。 至少一个输入二元组不全为0,因此分母对所有合法 A,BA,B 都为正。

输入格式

第一行两个整数 N,RN,R。 接下来 NN 行,每行两个整数 ai,bia_i,b_i。

输出格式

输出一行一个数,表示最大值,四舍五入保留六位小数。

样例

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

数据范围

1≤R≤N≤10001\le R\le N\le1000,0≤ai,bi≤1090\le a_i,b_i\le10^9,至少一个二元组不全为0。 30%的数据满足 N≤20N\le20,50%的数据满足 N≤50N\le50。

参考附件

原题资料(本页约定为准)