제곱근넘침(오버플로)소수 자리 출력P0233

배달 드론이 날아간 거리

배달 드론이 기지 (0, 0, 0)에서 떠나 배달할 곳 n군데를 주어진 차례대로 들른 뒤 기지로 돌아온다. 첫 줄에 배달할 곳의 수 n이 주어진다. 다음 n줄에는 들르는 차례대로 배달할 곳의 좌표 x, y, z(센티미터)가 빈칸으로 띄워 한 줄에 하나씩 주어진다. 드론은 한 곳에서 다음 곳까지 곧게 날아간다. 두 곳 사이의 거리는 x, y, z 차이를 각각 제곱해 더한 값의 제곱근이다. 구간은 n + 1개다: 1번 구간은 기지에서 첫 곳까지, k번 구간은 (k-1)째 곳에서 k째 곳까지, n + 1번 구간은 n째 곳에서 기지까지다. 같은 곳이 이어서 나오거나 기지와 같은 곳이 나올 수도 있고, 그러면 그 구간의 거리는 0이다. 1번 구간부터 n + 1번 구간까지, 구간을 하나 날 때마다 그때까지 날아간 거리의 합을 한 줄에 출력하라. 거리의 합은 소수 둘째 자리까지 반올림해 소수점 아래를 정확히 두 자리로 쓴다(5는 5.00). 반올림이 헷갈리지 않도록, 출력할 모든 합은 100을 곱했을 때 소수 부분이 0.4 이상 0.6 이하가 되지 않게 주어진다. 마지막 줄에는 가장 긴 구간의 번호를 출력하라. 가장 긴 구간이 여럿이면 그중 번호가 가장 작은 것을 출력한다.

입력: 1 ≤ n ≤ 1,000, -1,000,000 ≤ x, y ≤ 1,000,000, 0 ≤ z ≤ 100,000(모두 정수), 출력할 합 × 100의 소수 부분이 0.4~0.6인 입력은 없다
출력: n + 1줄: 구간마다 그때까지의 거리 합(소수 둘째 자리까지) / 마지막 줄: 가장 긴 구간의 번호

예시 1 · stdin

2
3 4 0
3 4 12

stdout

예시 2 · stdin

stdout

main.py 프로그래밍 언어 실행 판

입력(stdin)

실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).

$ 준비됐어요

코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.

다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이

제곱근은 Python math.sqrt(또는 ** 0.5), JS·TS Math.sqrt, Java Math.sqrt, C# Math.Sqrt, C sqrt(<math.h>, 링크할 때 -lm), C++ std::sqrt(<cmath>), 크레이콘 수학.제곱근이에요.
모두 double을 돌려주니 long len = sqrt(...)처럼 정수 변수에 담으면 5.83이 5가 돼요.
제곱하기 전의 크기를 먼저 봐야 해요.
좌표 차이는 2×10^6까지라 제곱하면 4×10^12이고, 32비트 int는 차이가 46,341 이상이기만 해도 제곱이 넘쳐요.
Java·C#은 좌표를 long으로, C·C++은 long long으로 읽어서 곱해요.
Python 정수는 크기 제한이 없고, JS·TS·크레이콘의 수는 2^53까지 정수가 정확해서 세 제곱의 합(약 8×10^12)도 그대로 맞아요.
합은 C float이나 C# float로 쌓으면 유효숫자가 일곱 자리쯤이라 수십억 센티미터에서 소수 자리가 틀려요.
double을 써요.
출력은 Python f"{total:.2f}", JS·TS toFixed(2), Java String.format(Locale.ROOT, "%.2f", total), C# ToString("F2", CultureInfo.InvariantCulture), C·C++ printf("%.2f"), 크레이콘 글자.소수자리맞추기(total, 2)예요.
Math.floor(total * 100) / 100처럼 내리면 반올림이 아니라 버림이 돼요.
가장 긴 구간은 제곱근을 구하지 않고 정수인 제곱의 합끼리 비교해도 되고, 그러면 실수 오차를 생각할 필요가 없어요.
>로 비교해야 같은 길이일 때 앞 번호가 남아요.
기지로 돌아오는 n + 1번 구간을 빠뜨리지 않게, 좌표 목록 끝에 (0, 0, 0)을 하나 더 붙이면 반복 하나로 끝나요.

Pythonmain.py · 18 줄

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 줄

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 줄

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 줄

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 줄

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 줄

#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 줄

#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 줄

n = 콘솔.줄읽기().수로변환();cx = 0;cy = 0;cz = 0;total = 0;best = 1;bestSq = -1;반복 (i = 1; i <= n + 1; i++){    // 마지막(n + 1번째) 구간은 기지 (0, 0, 0)으로 돌아오는 길    p = [0, 0, 0];    만약 (i <= n)    {        p = 콘솔.수들읽기();    }    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 += 수학.제곱근(sq);    콘솔.쓰기(글자.소수자리맞추기(total, 2));    만약 (sq > bestSq)    {        best = i;        bestSq = sq;    }    cx = p[0];    cy = p[1];    cz = p[2];}콘솔.쓰기(best);