题目详情题解（0）讨论（0）提交记录（0）

AT_abc375_b.[ABC375B] Traveling Takahashi Problem

入门

通过率：0%

AC君温馨提醒

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

题目描述

在二维坐标平面上的原点有高桥君。

高桥君从坐标平面上的点 (a,b)(a,b) 移动到点 (c,d)(c,d) 时，需要花费的代价为 (a−c)2+(b−d)2\sqrt{(a-c)^2+(b-d)^2}。

请计算高桥君从原点出发，依次经过 NN 个点 (X1,Y1),…,(XN,YN)(X_1,Y_1),\ldots,(X_N,Y_N)，最后返回原点时，所需的总代价。

输入格式

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

NN
X1X_1 Y1Y_1
⋮\vdots
XNX_N YNY_N

输出格式

请输出答案。
只要与真实值的相对误差或绝对误差不超过 10−610^{-6}，即可视为正确。

输入输出样例

  • 输入#1

    2
1 2
-1 0

    输出#1

    6.06449510224597979401

  • 输入#2

    7
-14142 13562
-17320 50807
-22360 67977
24494 89742
-26457 51311
28284 27124
31622 77660

    输出#2

    384694.57587932075868509383

  • 输入#3

    5
-100000 100000
100000 -100000
-100000 100000
100000 -100000
-100000 100000

    输出#3

    1414213.56237309504880168872

说明/提示

限制条件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • −109≤Xi,Yi≤109-10^9 \leq X_i, Y_i \leq 10^9
  • 输入均为整数

样例解释 1

移动分为以下 33 个阶段。

  • 从 (0,0)(0,0) 移动到 (1,2)(1,2)。代价为 (0−1)2+(0−2)2=5=2.236067977…\sqrt{(0-1)^2+(0-2)^2} = \sqrt{5} = 2.236067977\ldots
  • 从 (1,2)(1,2) 移动到 (−1,0)(-1,0)。代价为 (1−(−1))2+(2−0)2=8=2.828427124…\sqrt{(1-(-1))^2+(2-0)^2} = \sqrt{8} = 2.828427124\ldots
  • 从 (−1,0)(-1,0) 移动回 (0,0)(0,0)。代价为 (−1−0)2+(0−0)2=1=1\sqrt{(-1-0)^2+(0-0)^2} = \sqrt{1} = 1
    总代价为 6.064495102…6.064495102\ldots。

由 ChatGPT 4.1 翻译

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

首页