题目链接

绕距

题目描述

计算城市中两点 (x1, y1) 和 (x2, y2) 之间的"绕距"。绕距被定义为两点间的曼哈顿距离与欧几里得距离之差的绝对值。

  • 欧几里得距离: sqrt((x1 - x2)² + (y1 - y2)²)
  • 曼哈顿距离: |x1 - x2| + |y1 - y2|
  • 绕距: |曼哈顿距离 - 欧几里得距离|

输入描述:

  • 第一行输入两个整数 x1, y1，表示起点坐标。
  • 第二行输入两个整数 x2, y2，表示终点坐标。

输出描述: 输出一个实数，表示两点间的绕距。答案与标准答案误差不超过 1e-4 即可。

解题思路

本题的核心是根据给定的公式，准确计算两种距离，然后求其差的绝对值。

  1. 读取坐标：读取起点和终点的四个坐标值 x1, y1, x2, y2。
  2. 计算坐标差：为了方便计算，先求出横纵坐标的差值，dx = |x1 - x2| 和 dy = |y1 - y2|。
  3. 计算曼哈顿距离：根据公式，曼哈顿距离就是 dx + dy。
  4. 计算欧几里得距离：根据公式，欧几里得距离是 sqrt(dx² + dy²)。这里需要使用 sqrt 函数，并且所有计算都应在浮点数（如 double）环境下进行，以保证精度。
  5. 计算并输出绕距：最后，计算 |曼哈顿距离 - 欧几里得距离| 并输出。由于是浮点数计算，直接输出结果即可满足精度要求。

代码

#include <iostream>
#include <cmath>     // For sqrt and fabs
#include <iomanip>   // For setprecision

using namespace std;

int main() {
    double x1, y1, x2, y2;
    // 读取两点坐标
    cin >> x1 >> y1 >> x2 >> y2;

    // 计算坐标差的绝对值
    double dx = fabs(x1 - x2);
    double dy = fabs(y1 - y2);

    // 计算曼哈顿距离
    double manhattan_dist = dx + dy;
    // 计算欧几里得距离
    double euclidean_dist = sqrt(dx * dx + dy * dy);

    // 计算并输出绕距
    cout << fixed << setprecision(18) << fabs(manhattan_dist - euclidean_dist) << endl;

    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取两点坐标
        double x1 = sc.nextDouble();
        double y1 = sc.nextDouble();
        double x2 = sc.nextDouble();
        double y2 = sc.nextDouble();

        // 计算坐标差的绝对值
        double dx = Math.abs(x1 - x2);
        double dy = Math.abs(y1 - y2);

        // 计算曼哈顿距离
        double manhattan_dist = dx + dy;
        // 计算欧几里得距离
        double euclidean_dist = Math.sqrt(dx * dx + dy * dy);

        // 计算并输出绕距
        System.out.println(Math.abs(manhattan_dist - euclidean_dist));
    }
}

import math

# 读取坐标
x1, y1 = map(int, input().split())
x2, y2 = map(int, input().split())

# 计算坐标差的绝对值
dx = abs(x1 - x2)
dy = abs(y1 - y2)

# 计算曼哈顿距离
manhattan_dist = dx + dy
# 计算欧几里得距离
euclidean_dist = math.sqrt(dx**2 + dy**2)

# 计算并输出绕距
print(abs(manhattan_dist - euclidean_dist))

算法及复杂度

  • 算法：几何距离计算。
  • 时间复杂度： - 仅涉及常数时间的算术运算。
  • 空间复杂度： - 仅需常数空间存储变量。