CF142E.Help Greg the Dwarf 2

NOI/NOI+/CTSC

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

Greg the Dwarf has been really busy recently with excavations by the Neverland Mountain. However for the well-known reasons (as you probably remember he is a very unusual dwarf and he cannot stand sunlight) Greg can only excavate at night. And in the morning he should be in his crypt before the first sun ray strikes. That's why he wants to find the shortest route from the excavation point to his crypt. Greg has recollected how the Codeforces participants successfully solved the problem of transporting his coffin to a crypt. So, in some miraculous way Greg appeared in your bedroom and asks you to help him in a highly persuasive manner. As usual, you didn't feel like turning him down.

After some thought, you formalized the task as follows: as the Neverland mountain has a regular shape and ends with a rather sharp peak, it can be represented as a cone whose base radius equals r and whose height equals h. The graveyard where Greg is busy excavating and his crypt can be represented by two points on the cone's surface. All you've got to do is find the distance between points on the cone's surface.

The task is complicated by the fact that the mountain's base on the ground level and even everything below the mountain has been dug through by gnome (one may wonder whether they've been looking for the same stuff as Greg...). So, one can consider the shortest way to pass not only along the side surface, but also along the cone's base (and in a specific case both points can lie on the cone's base — see the first sample test)

Greg will be satisfied with the problem solution represented as the length of the shortest path between two points — he can find his way pretty well on his own. He gave you two hours to solve the problem and the time is ticking!

矮人格雷格最近一直在永无乡山脉进行挖掘工作。但由于众所周知的原因(你可能还记得,他是一位非常特别的矮人,无法忍受阳光),格雷格只能在夜间进行挖掘;而到了清晨,他必须在第一缕阳光照射到之前回到自己的墓穴中。因此,他希望找到从挖掘点到其墓穴的最短路径。格雷格回想起 Codeforces 参赛者曾成功解决过将他的棺材运送到墓穴的问题,于是以某种不可思议的方式,他突然出现在你的卧室里,并以极具说服力的方式请求你帮助他。和往常一样,你实在难以拒绝他的请求。

经过一番思考,你将该任务形式化如下:由于永无乡山脉具有规则的外形,且顶部较为尖锐,因此可将其建模为一个底面半径为 rr、高为 hh 的圆锥。格雷格正在挖掘的墓地及其墓穴可表示为该圆锥表面上的两个点。你所需要做的,就是求出这两个点在圆锥表面上的最短距离。

该任务的复杂性在于:山体底部的地表乃至山体下方的所有区域均已被地精挖空(人们不禁要问:他们是否也在寻找与格雷格相同的东西……?)。因此,最短路径不仅可沿圆锥的侧表面行进,也可沿圆锥的底面行进(在特定情形下,两个点甚至可能都位于圆锥底面上——参见第一个样例测试)。

格雷格只需你给出两点间最短路径的长度即可满意(他完全可以凭此自行找到路线)。他给了你两小时来解决这个问题,而时间正在飞速流逝!

输入格式

The first input line contains space-separated integers r and h (1 ≤ r, h ≤ 1000) — the base radius and the cone height correspondingly. The second and third lines contain coordinates of two points on the cone surface, groups of three space-separated real numbers. The coordinates of the points are given in the systems of coordinates where the origin of coordinates is located in the centre of the cone's base and its rotation axis matches the OZ axis. In this coordinate system the vertex of the cone is located at the point (0, 0, h), the base of the cone is a circle whose center is at the point (0, 0, 0), lying on the XOY plane, and all points on the cone surface have a non-negative coordinate z. It is guaranteed that the distances from the points to the cone surface do not exceed 10 - 12. All real numbers in the input have no more than 16 digits after decimal point.

第一行输入包含两个用空格分隔的整数 rr 和 hh(1≤r,h≤10001 \leq r, h \leq 1000),分别表示圆锥底面半径和高。
第二行与第三行各包含一个位于圆锥表面上的点的坐标,每行均为三个用空格分隔的实数。
这些点的坐标是在如下坐标系中给出的:坐标原点位于圆锥底面中心,圆锥的旋转轴与 OZOZ 轴重合。在此坐标系中,圆锥顶点位于点 (0, 0, h)(0,\,0,\,h),圆锥底面是一个以点 (0, 0, 0)(0,\,0,\,0) 为圆心、位于 XOYXOY 平面上的圆,且圆锥表面上所有点的 zz 坐标均非负。
保证所给两点到圆锥表面的距离不超过 10−1210^{-12}。输入中的所有实数小数点后至多有 16 位数字。

输出格式

Print the length of the shortest path between the points given in the input, with absolute or relative error not exceeding 10 - 6.

输出输入中给定点之间的最短路径长度,绝对或相对误差不超过 10−610^{-6}。

输入输出样例

  • 输入#1

    2 2
    1.0 0.0 0.0
    -1.0 0.0 0.0

    输出#1

    2.000000000
  • 输入#2

    2 2
    1.0 0.0 0.0
    1.0 0.0 1.0

    输出#2

    2.414213562
  • 输入#3

    2 2
    1.0 0.0 1.0
    -1.0 0.0 1.0

    输出#3

    2.534324263
  • 输入#4

    2 2
    1.0 0.0 0.0
    0.0 1.0 1.0

    输出#4

    3.254470198

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

首页