square rootoverflowprinting decimalsP0233

How far the delivery drone flew

A delivery drone leaves its base (0, 0, 0), visits n delivery spots in the given order and returns to the base. The first line gives the number of spots n. Each of the next n lines gives one spot's coordinates x, y, z (centimetres), separated by spaces, in visiting order. The drone flies in a straight line from one place to the next. The distance between two places is the square root of the sum of the squared differences in x, y and z. There are n + 1 legs: leg 1 goes from the base to the first spot, leg k from the (k-1)-th spot to the k-th, and leg n + 1 from the n-th spot back to the base. The same spot may appear twice in a row, or a spot may equal the base; such a leg has distance 0. From leg 1 to leg n + 1, after each leg print the total distance flown so far on its own line. Round each total to two decimal places and write exactly two digits after the decimal point (5 is 5.00). To keep rounding unambiguous, every total to print is such that its fractional part after multiplying by 100 is not between 0.4 and 0.6 inclusive. On the last line print the number of the longest leg. If several legs share the greatest length, print the smallest of their numbers.

Input: 1 ≤ n ≤ 1,000, -1,000,000 ≤ x, y ≤ 1,000,000, 0 ≤ z ≤ 100,000 (all integers), no total to print has a fractional part of total × 100 in 0.4–0.6
Output: n + 1 lines: the running total after each leg (two decimals) / last line: the number of the longest leg

Example 1 · stdin

2
3 4 0
3 4 12

stdout

Example 2 · stdin

stdout

main.py Programming language Runtime version

Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 8 languages

Square root is Python math.sqrt (or ** 0.5), JS/TS Math.sqrt, Java Math.sqrt, C# Math.Sqrt, C sqrt (<math.h>, link with -lm), C++ std::sqrt (<cmath>) and Craykon Mathf.Sqrt.
They all return a double, so storing the result in an integer as in long len = sqrt(...) turns 5.83 into 5.
Check the size before squaring.
Coordinate differences reach 2×10^6, so a square reaches 4×10^12, and a 32-bit int overflows as soon as a difference reaches 46,341.
Java and C# read the coordinates as long, and C and C++ as long long, before multiplying.
Python integers have no size limit, and numbers in JS, TS and Craykon are exact integers up to 2^53, so even the sum of three squares (about 8×10^12) stays exact.
Accumulating the total in a C or C# float keeps only about seven significant digits, so the decimals go wrong at billions of centimetres.
Use double.
Printing is Python f"{total:.2f}", JS/TS toFixed(2), Java String.format(Locale.ROOT, "%.2f", total), C# ToString("F2", CultureInfo.InvariantCulture), C/C++ printf("%.2f") and Craykon Str.Fixed(total, 2).
Rounding down with Math.floor(total * 100) / 100 truncates instead of rounding.
For the longest leg you can compare the integer sums of squares without taking square roots, so floating-point error never enters.
Compare with > so the earlier number stays on a tie.
To avoid forgetting leg n + 1 back to the base, append one more (0, 0, 0) to the list of spots and a single loop does it all.

Pythonmain.py · 18 lines

import math n = int(input())points = [tuple(map(int, input().split())) for _ in range(n)]points.append((0, 0, 0))  # 마지막 구간은 기지로 돌아오는 길 cur = (0, 0, 0)total = 0.0best, best_sq = 1, -1for i, p in enumerate(points, start=1):    dx, dy, dz = p[0] - cur[0], p[1] - cur[1], p[2] - cur[2]    sq = dx * dx + dy * dy + dz * dz  # 정수 그대로 비교한다    total += math.sqrt(sq)    print(f"{total:.2f}")    if sq > best_sq:        best, best_sq = i, sq    cur = pprint(best)

JavaScriptmain.js · 26 lines

const nums = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = nums[0];const points = [];for (let i = 0; i < n; i++) points.push(nums.slice(1 + 3 * i, 4 + 3 * i));points.push([0, 0, 0]); // 마지막 구간은 기지로 돌아오는 길 let cur = [0, 0, 0];let total = 0;let best = 1;let bestSq = -1;const out = [];points.forEach((p, i) => {  const dx = p[0] - cur[0];  const dy = p[1] - cur[1];  const dz = p[2] - cur[2];  const sq = dx * dx + dy * dy + dz * dz; // 최대 약 8×10^12: 2^53 안이라 정확하다  total += Math.sqrt(sq);  out.push(total.toFixed(2));  if (sq > bestSq) {    best = i + 1;    bestSq = sq;  }  cur = p;});out.push(best);console.log(out.join("\n"));

TypeScriptmain.ts · 28 lines

import { readFileSync } from "node:fs";const nums: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = nums[0];type Point = [number, number, number];const points: Point[] = [];for (let i = 0; i < n; i++) points.push([nums[1 + 3 * i], nums[2 + 3 * i], nums[3 + 3 * i]]);points.push([0, 0, 0]); // 마지막 구간은 기지로 돌아오는 길 let cur: Point = [0, 0, 0];let total = 0;let best = 1;let bestSq = -1;const out: string[] = [];points.forEach((p, i) => {  const dx = p[0] - cur[0];  const dy = p[1] - cur[1];  const dz = p[2] - cur[2];  const sq = dx * dx + dy * dy + dz * dz; // 최대 약 8×10^12: 2^53 안이라 정확하다  total += Math.sqrt(sq);  out.push(total.toFixed(2));  if (sq > bestSq) {    best = i + 1;    bestSq = sq;  }  cur = p;});out.push(String(best));console.log(out.join("\n"));

JavaMain.java · 36 lines

import java.util.Locale;import java.util.Scanner; public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int n = sc.nextInt();        long cx = 0, cy = 0, cz = 0;        double total = 0;        int best = 1;        long bestSq = -1;        StringBuilder out = new StringBuilder();        for (int i = 1; i <= n + 1; i++) {            // 마지막(n + 1번째) 구간은 기지 (0, 0, 0)으로 돌아오는 길            long x = 0, y = 0, z = 0;            if (i <= n) {                x = sc.nextLong();                y = sc.nextLong();                z = sc.nextLong();            }            long dx = x - cx, dy = y - cy, dz = z - cz;            long sq = dx * dx + dy * dy + dz * dz; // 차이가 2×10^6이면 제곱은 4×10^12: long이 필요하다            total += Math.sqrt(sq);            out.append(String.format(Locale.ROOT, "%.2f", total)).append('\n');            if (sq > bestSq) {                best = i;                bestSq = sq;            }            cx = x;            cy = y;            cz = z;        }        out.append(best).append('\n');        System.out.print(out);    }}

C#Main.cs · 42 lines

using System;using System.Globalization;using System.Text; class Program{    static void Main()    {        int n = int.Parse(Console.ReadLine());        long cx = 0, cy = 0, cz = 0;        double total = 0;        int best = 1;        long bestSq = -1;        var out_ = new StringBuilder();        for (int i = 1; i <= n + 1; i++)        {            // 마지막(n + 1번째) 구간은 기지 (0, 0, 0)으로 돌아오는 길            long x = 0, y = 0, z = 0;            if (i <= n)            {                string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);                x = long.Parse(p[0]);                y = long.Parse(p[1]);                z = long.Parse(p[2]);            }            long dx = x - cx, dy = y - cy, dz = z - cz;            long sq = dx * dx + dy * dy + dz * dz; // 차이가 2×10^6이면 제곱은 4×10^12: long이 필요하다            total += Math.Sqrt(sq);            out_.Append(total.ToString("F2", CultureInfo.InvariantCulture)).Append('\n');            if (sq > bestSq)            {                best = i;                bestSq = sq;            }            cx = x;            cy = y;            cz = z;        }        out_.Append(best).Append('\n');        Console.Write(out_);    }}

C++main.cpp · 29 lines

#include <cmath>#include <cstdio>#include <iostream> int main() {    int n;    std::cin >> n;    long long cx = 0, cy = 0, cz = 0;    double total = 0;    int best = 1;    long long bestSq = -1;    for (int i = 1; i <= n + 1; i++) {        // 마지막(n + 1번째) 구간은 기지 (0, 0, 0)으로 돌아오는 길        long long x = 0, y = 0, z = 0;        if (i <= n) std::cin >> x >> y >> z;        long long dx = x - cx, dy = y - cy, dz = z - cz;        long long sq = dx * dx + dy * dy + dz * dz; // 제곱은 4×10^12까지: long long        total += std::sqrt(static_cast<double>(sq));        std::printf("%.2f\n", total);        if (sq > bestSq) {            best = i;            bestSq = sq;        }        cx = x;        cy = y;        cz = z;    }    std::printf("%d\n", best);}

Cmain.c · 29 lines

#include <math.h>#include <stdio.h> int main(void) {    int n;    scanf("%d", &n);    long long cx = 0, cy = 0, cz = 0;    double total = 0; /* float는 일곱 자리쯤에서 끝나 소수 둘째 자리를 지킬 수 없다 */    int best = 1;    long long best_sq = -1;    for (int i = 1; i <= n + 1; i++) {        /* 마지막(n + 1번째) 구간은 기지 (0, 0, 0)으로 돌아오는 길 */        long long x = 0, y = 0, z = 0;        if (i <= n) scanf("%lld %lld %lld", &x, &y, &z);        long long dx = x - cx, dy = y - cy, dz = z - cz;        long long sq = dx * dx + dy * dy + dz * dz; /* 제곱은 4×10^12까지: long long */        total += sqrt((double)sq);        printf("%.2f\n", total);        if (sq > best_sq) {            best = i;            best_sq = sq;        }        cx = x;        cy = y;        cz = z;    }    printf("%d\n", best);    return 0;}

Craykonmain.cray · 31 lines

n = Console.ReadLine().ToNumber();cx = 0;cy = 0;cz = 0;total = 0;best = 1;bestSq = -1;for (i = 1; i <= n + 1; i++){    // 마지막(n + 1번째) 구간은 기지 (0, 0, 0)으로 돌아오는 길    p = [0, 0, 0];    if (i <= n)    {        p = Console.ReadNumbers();    }    dx = p[0] - cx;    dy = p[1] - cy;    dz = p[2] - cz;    sq = dx * dx + dy * dy + dz * dz; // 최대 약 8×10^12: 2^53 안이라 정확하다    total += Mathf.Sqrt(sq);    Console.WriteLine(Str.Fixed(total, 2));    if (sq > bestSq)    {        best = i;        bestSq = sq;    }    cx = p[0];    cy = p[1];    cz = p[2];}Console.WriteLine(best);