PDI+VC · Exercício de Programação

EP01_01 — 📏 Três métricas de distância em PDI

1.17.1 EP01_01 📏 Três métricas de distância em PDI

Nesta atividade, você deve escrever um programa que calcule as três distâncias clássicas em PDI: Euclidiana (L2), City‑Block (L1) e Chessboard (L∞).

  • Leia 4 números reais que representam as coordenadas: \(A_x, A_y, B_x, B_y\).
  • Calcule as três distâncias utilizando as 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)\]

  • Imprima os três resultados, cada um em uma linha, formatados com duas casas decimais, na ordem: Euclidiana, City‑block, Chessboard.

📌 Importante:

  • Utilize as funções matemáticas padrão da sua linguagem: math.sqrt, abs (ou fabs) e max.
  • A saída deve conter apenas os números (um por linha), sem textos adicionais.
  • Ver um simulador interativo para esta questão na Figura 1.11 (gráfico com arrasto dos pontos e visualização das três métricas).

1.17.1.1 🖼️ Por que isso importa? – Custo computacional

Em uma imagem 1000×1000 pixels (1 milhão de pixels), calcular a distância de cada pixel a um ponto de referência exige 1 milhão de operações. A escolha da métrica afeta o desempenho:

Métrica Operações por pixel Custo relativo (1M pixels) Quando usar
Euclidiana (L2) 2 subtrações, 2 multiplicações, 1 soma, 1 sqrt 🔴 Mais custosa – sqrt é cara Distância “real” no espaço contínuo
City‑block (L1) 2 subtrações, 2 abs, 1 soma 🟡 Moderada – sem raiz quadrada Grids, robótica, imagens binárias
Chessboard (L∞) 2 subtrações, 2 abs, 1 max 🟢 Mais eficiente Movimentos de peças, morfologia

A função sqrt é computacionalmente mais cara que operações como adição, subtração, multiplicação e valor absoluto. Em CPUs modernas, a diferença pode ser pequena (cerca de 1,5× a 3×), mas em sistemas embarcados ou em laços de milhões de iterações, qualquer ganho importa. Por isso, quando o objetivo é apenas comparar distâncias (ex.: encontrar o ponto mais próximo), use a distância euclidiana ao quadrado.

1.17.1.2 📋 Tarefa (especificação para VPL)

Entrada:
Uma única linha com quatro números reais: Ax Ay Bx By

Saída:
Três linhas, cada uma com um número real de duas casas decimais (Euclidiana, City‑block, Chessboard).

1.17.1.3 📌 Exemplos

Entrada Saída Observação
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 unitária

Exemplo de teste de sqrt em Python, com timeit isolando cada operação:

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

// Compile: g++ -O2 -o benchmark benchmark.cpp -lm

constexpr int N = 50'000'000;

double apenas_soma() {
    double a = 3.0, b = 4.0;
    return a + b;
}

double soma_e_sqrt() {
    double a = 3.0, b = 4.0;
    return std::sqrt(a*a + b*b);
}

int main() {
    // Medição da soma simples
    auto start_soma = std::chrono::high_resolution_clock::now();
    volatile double resultado_soma = 0;
    for (int i = 0; i < N; ++i) {
        resultado_soma = apenas_soma();
    }
    auto end_soma = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> t_soma = end_soma - start_soma;

    // Medição da soma + sqrt
    auto start_sqrt = std::chrono::high_resolution_clock::now();
    volatile double resultado_sqrt = 0;
    for (int i = 0; i < N; ++i) {
        resultado_sqrt = soma_e_sqrt();
    }
    auto end_sqrt = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> t_sqrt = end_sqrt - start_sqrt;

    std::cout << "Soma simples       : " << t_soma.count() << " s" << std::endl;
    std::cout << "Soma + sqrt        : " << t_sqrt.count() << " s" << std::endl;
    std::cout << "Razão (sqrt/soma)  : " << t_sqrt.count() / t_soma.count() << "x" << std::endl;

    // Evita otimização do compilador
    std::cout << "Resultados: " << resultado_soma << " " << resultado_sqrt << std::endl;

    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.144417 s
Soma + sqrt        : 0.209864 s
Razão (sqrt/soma)  : 1.45318x
Resultados: 7 5
🎮 Simulador EP01_01: Métricas de Distância no Espaço Discreto Euclidiana vs City-block vs Chessboard

Clique e arraste os pontos A ou B no plano cartesiano ou ajuste suas coordenadas abaixo para comparar as três métricas de distância em tempo real.

📐 EUCLIDIANA (L2)
5.00
√(Δx² + Δy²)
🧱 CITY-BLOCK (L1)
7.00
|Δx| + |Δy|
🏁 CHESSBOARD (L∞)
4.00
max(|Δx|, |Δy|)
👆 Arraste os pontos A (Roxo) ou B (Laranja) na grade.
Ponto A
Ponto B
Legenda Geométrica: Linha tracejada (Euclidiana), Caminho ortogonal em L (City-block) e Destaque da dimensão máxima (Chessboard).
Euclidiana City-block Chessboard (Máx)
Figura 1.11: Simulador EP01_01: Distâncias Euclidiana, City-block e Chessboard