bzoj#P2765. [JLOI2010]铁人双项比赛

[JLOI2010]铁人双项比赛

题目描述

铁人双项比赛是吉林教育学院的一项传统体育项目。

该项目比赛由长跑和骑自行车组成,参赛选手必须先完成k公里的长跑,然后完成 rr 公里的骑车,才能到达终点。

每个参赛选手所擅长的项目不同,有的擅长长跑,有的擅长骑车。

如果总赛程 s=k+rs=k+r 一定,那么 kk 越大,对擅长长跑的选手越有利;kk 越小,对擅长骑车的选手越有利。

现在给定总赛程 ss,以及每个选手长跑和骑车的平均速度,请你求出对于某个指定的选手最有利的 kkrr

所谓最有利,是指选择了这个 kkrr 后,该选手可以获得冠军,且领先第 22 名尽量地多。

输入格式

你的程序从文件读入输入数据。
输入的第一行是两个正整数 ssnnss 表示总赛程(单位为公里),nn 表示参赛总人数。
接下来的 nn 行每行是两个实数,分别表示每个选手长跑的平均速度和骑车的平均速度(单位为千米/小时)。
nn 个选手就是指定的选手,你的任务是求出对他最有利的 kkrr

输出格式

你的程序的输出包括三个数 k,r,tk,r,t,分别表示对第 nn 号选手最有利的 kkrr(浮点数,保留小数点后 22 位),以及在选择 kkrr 的情况下,第 nn 号选手最多可以领先第 22 名多少秒(四舍五入到整数);如果另一个选手和该选手并列第一,则 ti=0t_i=0。倘若无论选择什么 k,rk,r 都不能使第 nn 号选手获胜,则输出 NO

100  3
10.0  40.0
20.0  30.0
15.0  35.0
14.29  85.71  612

数据规模与约定

对于 100%100\% 的数据,s231s\leq2^{31}2n1002 \leq n \leq 100