AT_arc049_b.[ARC049B] 高橋ノルム君

提高+/省选-

通过率：0%

AC君温馨提醒

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

题目描述

高桥诺姆君的可能性是无限大的。名为高桥诺姆的人在这个世界上有很多。

在二维平面上有 $N$ 个高桥诺姆君。第 $i$ 个高桥诺姆君（ $1 \leq i \leq N$ ）位于坐标 $(x_i, y_i)$ 。每个高桥诺姆君都有一个正整数常数 $c_i$ ，第 $i$ 个高桥诺姆君移动到某点 $(X, Y)$ 需要的时间为 $c_i \times \max(|x_i - X|, |y_i - Y|)$ 。

你的任务是求出让所有高桥诺姆君聚集到同一点所需的最小时间。这里，所需的最小时间指的是到达该点最慢的高桥君所花费的时间。

所有高桥诺姆君会同时开始移动，且互不干扰。

输入格式

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

$N$
$x_1\ y_1\ c_1$
$x_2\ y_2\ c_2$
$\vdots$
$x_N\ y_N\ c_N$

第 $1$ 行给出高桥诺姆君的数量 $N$ ，其中 $2 \leq N \leq 1,000$ 。
接下来的 $N$ 行中，第 $i$ 行给出第 $i$ 个高桥君在二维平面上的位置和常数，分别为 $3$ 个整数 $x_i, y_i, c_i$ ，以空格分隔。 $-10^5 \leq x_i, y_i \leq 10^5, 1 \leq c_i \leq 1,000$ 。
可能有多个高桥诺姆君在同一坐标。

输出格式

输出让所有高桥诺姆君聚集到同一点所需的最小时间。只要绝对误差或相对误差不超过 $10^{-4}$ 即视为正确。输出末尾需换行。

输入输出样例

输入#1
```
2
0 0 1
10 10 1
```
输出#1
```
5.000000000000000
```
输入#2
```
2
0 0 1
10 10 2
```
输出#2
```
6.666666666666667
```

输入#3

输出#3

582.222222222222222

输入#4

8
-81739 73917 446
42230 30484 911
79354 -50126 200
33440 -47087 651
-73 84114 905
79222 -53608 713
65194 -46284 685
81145 40933 47

输出#4

54924095.383189122374461

说明/提示

部分分

本题设有部分分。

若对于任意 $i(1 \leq i \leq N)$ ， $c_i=1$ 的数据集答对，则可获得 $30$ 分。
若在无额外限制的数据集上答对，则可获得上述以外的 $70$ 分。

样例解释 1

如果集合点选在 $(5,5)$ ，两个人都能在 $5$ 秒内到达该点，这就是最小值。

由 ChatGPT 4.1 翻译

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

首页