CF424B.Megacity

普及-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

The administration of the Tomsk Region firmly believes that it's time to become a megacity (that is, get population of one million). Instead of improving the demographic situation, they decided to achieve its goal by expanding the boundaries of the city.

The city of Tomsk can be represented as point on the plane with coordinates (0; 0). The city is surrounded with n other locations, the i-th one has coordinates (x__i, y__i) with the population of k__i people. You can widen the city boundaries to a circle of radius r. In such case all locations inside the circle and on its border are included into the city.

Your goal is to write a program that will determine the minimum radius r, to which is necessary to expand the boundaries of Tomsk, so that it becomes a megacity.

托木斯克州政府坚信,该市已到了成为“超大城市”(即人口达到一百万)的时候。与其改善人口状况,他们决定通过扩大城市边界来实现这一目标。

托木斯克市可表示为平面上坐标为 (0,0)(0, 0) 的一个点。该市周围分布着 nn 个其他地点,其中第 ii 个地点的坐标为 (xi,yi)(x_i, y_i),人口为 kik_i 人。你可以将城市边界扩展为一个半径为 rr 的圆;此时,所有位于该圆内部及圆周上的地点都将被纳入城市范围。

你的任务是编写一个程序,确定使托木斯克成为超大城市所需扩展的最小半径 rr。

输入格式

The first line of the input contains two integers n and s (1 ≤ n ≤ 103; 1 ≤ s < 106) — the number of locatons around Tomsk city and the population of the city. Then n lines follow. The i-th line contains three integers — the x__i and y__i coordinate values of the i-th location and the number k__i of people in it (1 ≤ k__i < 106). Each coordinate is an integer and doesn't exceed 104 in its absolute value.

It is guaranteed that no two locations are at the same point and no location is at point (0; 0).

输入的第一行包含两个整数 nn 和 ss(1≤n≤1031 \leq n \leq 10^3;1≤s<1061 \leq s < 10^6)—— 分别表示托木斯克市周边的地点数量和该市的人口总数。接下来是 nn 行,第 ii 行包含三个整数:第 ii 个地点的坐标 xix_i、yiy_i 以及该地点的人数 kik_i(1≤ki<1061 \leq k_i < 10^6)。每个坐标的绝对值均不超过 10410^4。

保证任意两个地点不位于同一点,且没有任何地点位于原点 (0,0)(0, 0)。

输出格式

In the output, print "-1" (without the quotes), if Tomsk won't be able to become a megacity. Otherwise, in the first line print a single real number — the minimum radius of the circle that the city needs to expand to in order to become a megacity.

The answer is considered correct if the absolute or relative error don't exceed 10 - 6.

如果托木斯克无法成为特大城市,则在输出中打印 -1(不带引号)。否则,在第一行输出一个实数——城市为成为特大城市所需扩展的最小圆半径。

若答案的绝对误差或相对误差均不超过 10−610^{-6},则视为正确。

输入输出样例

  • 输入#1

    4 999998
    1 1 1
    2 2 1
    3 3 1
    2 -2 1

    输出#1

    2.8284271
  • 输入#2

    4 999998
    1 1 2
    2 2 1
    3 3 1
    2 -2 1

    输出#2

    1.4142136
  • 输入#3

    2 1
    1 1 999997
    2 2 1

    输出#3

    -1

输入解题思路,AI测评打分。不知道怎么写?

首页