PDI+VC · Ejercicio de Programación

EP01_01 — 📏 Tres métricas de distancia en PDI

1.17.1 EP01_01 📏 Tres métricas de distancia en PDI

En esta actividad, debes escribir un programa que calcule las tres distancias clásicas en PDI: Euclidiana (L2), City‑Block (L1) y Chessboard (L∞).

  • Lee 4 números reales que representan las coordenadas: \(A_x, A_y, B_x, B_y\).
  • Calcula las tres distancias utilizando las fórmulas:

\[d_{\text{Euclidiana}} = \sqrt{(B_x - A_x)^2 + (B_y - A_y)^2}\]

\[d_{\text{City-block}} = |B_x - A_x| + |B_y - A_y|\]

\[d_{\text{Chessboard}} = \max\big(|B_x - A_x|,\; |B_y - A_y|\big)\]

  • Imprime los tres resultados, cada uno en una línea, formateados con dos cifras decimales, en el orden: Euclidiana, City‑block, Chessboard.

📌 Importante:

  • Utiliza las funciones matemáticas estándar de tu lenguaje: math.sqrt, abs (o fabs) y max.
  • La salida debe contener solo los números (uno por línea), sin textos adicionales.
  • Consulta un simulador interactivo para esta cuestión en la Figura 1.11 (gráfico con arrastre de los puntos y visualización de las tres métricas).

1.17.1.1 🖼️ ¿Por qué es importante? – Costo computacional

En una imagen 1000×1000 píxeles (1 millón de píxeles), calcular la distancia de cada píxel a un punto de referencia exige 1 millón de operaciones. La elección de la métrica afecta el rendimiento:

Métrica Operaciones por píxel Costo relativo (1M píxeles) Cuándo usar
Euclidiana (L2) 2 restas, 2 multiplicaciones, 1 suma, 1 sqrt 🔴 Más costosa – sqrt es cara Distancia “real” en el espacio continuo
City‑block (L1) 2 restas, 2 abs, 1 suma 🟡 Moderada – sin raíz cuadrada Cuadrículas, robótica, imágenes binarias
Chessboard (L∞) 2 restas, 2 abs, 1 max 🟢 Más eficiente Movimientos de piezas, morfología

La función sqrt es computacionalmente más cara que operaciones como suma, resta, multiplicación y valor absoluto. En CPUs modernas, la diferencia puede ser pequeña (alrededor de 1,5× a 3×), pero en sistemas embebidos o en bucles de millones de iteraciones, cualquier ganancia importa. Por eso, cuando el objetivo es solo comparar distancias (p. ej.: encontrar el punto más cercano), usa la distancia euclidiana al cuadrado.

1.17.1.2 📋 Tarea (especificación para VPL)

Entrada:
Una única línea con cuatro números reales: Ax Ay Bx By

Salida:
Tres líneas, cada una con un número real de dos cifras decimales (Euclidiana, City‑block, Chessboard).

1.17.1.3 📌 Ejemplos

Entrada Salida Observación
0
0
3
4		 5.00
7.00
4.00		 Triángulo 3‑4‑5
0
0
1
1		 1.41
2.00
1.00		 Diagonal unitaria

Ejemplo de prueba de sqrt en Python, con timeit aislando cada operación:

%%writefile tmp/mm_out_1.cpp
#include <iostream>
#include <cmath>
#include <chrono>

// Tiempo en segundos de una lambda
template <typename F>
double timeit(F&& f, int N) {
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) f();
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration<double>(end - start).count();
}

int main() {
    const int N = 50'000'000;

    // Solo suma
    auto apenas_soma = []() -> double {
        double a = 3.0, b = 4.0;
        return a + b;
    };

    // Suma y raíz cuadrada
    auto soma_e_sqrt = []() -> double {
        double a = 3.0, b = 4.0;
        return std::sqrt(a*a + b*b);
    };

    double t_soma = timeit(apenas_soma, N);
    double t_sqrt = timeit(soma_e_sqrt, N);

    std::cout.precision(3);
    std::cout << std::fixed;
    std::cout << "Soma simples       : " << t_soma << " s\n";
    std::cout << "Soma + sqrt        : " << t_sqrt << " s\n";
    std::cout << "Razão (sqrt/soma)  : " << (t_sqrt / t_soma) << "x\n";

    return 0;
}
Overwriting tmp/mm_out_1.cpp
!g++ -I. -std=c++17 tmp/mm_out_1.cpp -o tmp/mm_out_1 \
  && ./tmp/mm_out_1
Soma simples       : 0.123 s
Soma + sqrt        : 0.208 s
Razão (sqrt/soma)  : 1.685x
🎮 Simulador EP01_01: Métricas de Distancia en el Espacio Discreto Euclidiana vs City-block vs Chessboard

Haz clic y arrastra los puntos A o B en el plano cartesiano o ajusta sus coordenadas abajo para comparar las tres métricas de distancia en tiempo real.

📐 EUCLIDIANA (L2)
5.00
√(Δx² + Δy²)
🧱 CITY-BLOCK (L1)
7.00
|Δx| + |Δy|
🏁 CHESSBOARD (L∞)
4.00
max(|Δx|, |Δy|)
👆 Arrastra los puntos A (Morado) o B (Naranja) en la cuadrícula.
Punto A
Punto B
Leyenda Geométrica: Línea discontinua (Euclidiana), Camino ortogonal en L (City-block) y Resalte de la dimensión máxima (Chessboard).
Euclidiana City-block Chessboard (Máx)
Figura 1.11: Simulador EP01_01: Distancias Euclidiana, City-block y Chessboard