AT_relay2018_d.数直線

通过率：0%

AC君温馨提醒

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

题目描述

在数轴上有 $N$ 个点，第 $i$ 个点的坐标为 $x_i$ 。另外，给定 $N$ 个整数 $w_i$ 。

请你求出满足下述条件的点 $p$ 的坐标。如果有多个满足条件的点，请输出坐标最小的那个。

条件：对于所有满足 $1 \leq i \leq N$ 的整数 $i$ ， $(p$ 到第 $i$ 个点的距离 $) \times w_i$ 的最大值最小。

输入格式

输入以如下格式从标准输入给出。

$N$
$x_1$ $w_1$
$x_2$ $w_2$
$\vdots$
$x_N$ $w_N$

输出格式

输出满足条件的点 $p$ 的最小坐标。若你的输出的绝对误差或相对误差不超过 $10^{-9}$ ，则视为正确。

输入输出样例

输入#1

输出#1

0.500000000000

输入#2

20
-8965725 4915988
-8830129 1578539
-8356752 3503810
-7479989 5100308
-6995994 3722838
-6861764 3493854
-6486775 1657800
-4577872 7994227
-3685008 7178154
-3169623 9319261
-2694681 7493276
-1967934 3837689
-1634671 544297
-1232484 6010778
2733239 4318924
4797695 2789412
5713704 4416095
6609027 2426329
6997023 2155233
7812383 9912027

输出#2

2249873.278320866637

说明/提示

限制条件

$1 \leq N \leq 10^5$
$|x_i| \leq 10^7$
$x_i < x_{i+1}$ （ $1 \leq i \leq N-1$ ）
$1 \leq w_i \leq 10^7$
输入中所有值均为整数

样例解释 1

当点 $p$ 的坐标为 $0.5$ 时，对于每个点 $i$ （ $1 \leq i \leq N$ ）， $(p$ 到第 $i$ 个点的距离 $) \times w_i$ 的值分别为 $9.5,\ 6.5,\ 4.5,\ 0.5,\ 8.5,\ 9.5$ ，这些值的最大值为 $9.5$ 。无法使这个最大值更小，因此答案为 $0.5$ 。

由 ChatGPT 4.1 翻译

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

首页