Kelin Li

AOJ基础题 ITP1_10_D Distance II

Distance II

Your task is to calculate the distance between two n dimensional vectors x = {x1,x2,…,xn} and y = {y1,y2,…,yn}.

The Minkowski’s distance defined below is a metric which is a generalization of both the Manhattan distance and the Euclidean distance.
1
It can be the Manhattan distance where p = 1.
2
It can be the Euclidean distance where p = 2.
3

Also, it can be the Chebyshev distance where p = ∞.
4
Write a program which reads two n dimensional vectors x and y, and calculates Minkowski’s distance where p = 1, 2, 3, ∞ respectively.

Input

In the first line, an integer n is given. In the second and third line, x = {x1,x2,…,xn} and y = {y1,y2,…,yn} are given respectively. The elements in x and y are given in integers.

Output

Print the distance where p = 1,2,3 and ∞ in a line respectively. The output should not contain an absolute error greater than 10^-5.

Constraints

  • 1 ≤ n ≤ 100
  • 0 ≤ xi, yi ≤ 1000

Sample Input

3
1 2 3
2 0 4

Sample Output

4.000000
2.449490
2.154435
2.000000

問題を解く

  • 公式解法，很好的复习题，因为机器学习能用。
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <iomanip>

using namespace std;

int x[1001];
int y[1001];

void Minkowski(int n, int p)
{
    double temp = 0;
    double result = 0;
    double index = 1.0 / p;
    if (p == 4)
    {
        for (int i = 0; i < n; i++)
        {
            temp = abs(x[i] - y[i]);
            if (temp > result) result = temp;
            else continue;
        }
    }
    else 
    {
        for (int i = 0; i < n; i++)
        {
            temp += pow(abs(x[i] - y[i]), p);
        }
        result = pow(temp, index);
    }

    cout << fixed << setprecision(10);

    cout << result << endl;

}

void Matrix(int *m, int n)
{
    for (int i = 0; i < n; i++)
    {
        cin >> m[i];
    }
}

int main() {
    int n = 0;
    cin >> n;

    Matrix(x, n);
    Matrix(y, n);

    Minkowski(n, 1);
    Minkowski(n, 2);
    Minkowski(n, 3);
    Minkowski(n, 4);
}

总结

  • 闵可夫斯基距离又称LP距离；
  • 曼哈顿距离又称出租车距离，即走直角边（图形学像素点）；
  • 欧式距离即直线距离（相似度计算）；
  • 切比雪夫距离即绝对值距离（国际象棋）；
  • 转化：对于原坐标系中两点间的切比雪夫距离，是将坐标轴顺时针旋转45度并将所有点的坐标值放大sqrt(2)倍所得到的新坐标系中的曼哈顿距离的二分之一。
    5
←
→