1.16.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∞).

\[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)\]

📌 Importante:

1.16.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.16.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.16.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:

import math
import timeit

N = 50_000_000

def apenas_soma():
    a, b = 3.0, 4.0
    return a + b

def soma_e_sqrt():
    a, b = 3.0, 4.0
    return math.sqrt(a*a + b*b)

t_soma = timeit.timeit(apenas_soma, number=N)
t_sqrt = timeit.timeit(soma_e_sqrt, number=N)

print(f"Soma simples       : {t_soma:.3f} s")
print(f"Soma + sqrt        : {t_sqrt:.3f} s")
print(f"Razão (sqrt/soma)  : {t_sqrt/t_soma:.2f}x")
Soma simples       : 2.836 s
Soma + sqrt        : 5.602 s
Razão (sqrt/soma)  : 1.97x
🎮 Simulador: arraste os pontos ou use os controles ⚡ Euclidiana (√) ≈ mais custosa
📐 Euclidiana (L2)
5.00
√(Δx²+Δy²)
🧱 City‑Block (L1)
7.00
|Δx|+|Δy|
🏁 Chessboard (L∞)
4.00
max(|Δx|,|Δy|)
👆 clique e arraste os pontos A (roxo) ou B (laranja)
Ponto A
Ponto B
💡 O gráfico mostra: linha reta tracejada (Euclidiana), caminho em L (City‑Block) e o lado máximo contínuo (Chessboard).
Euclidiana City‑Block Chessboard (max)
Figura 1.12: Simulador: Distâncias Euclidiana, City-block e Chessboard

1.16.1.4 🐍 Python

Basta criar uma célula de código normal e inserir o código Python. A entrada pode ser simulada usando input(), que funciona normalmente.

Exemplo de célula:

%%writefile EP01_01.py
# Código Python
x1,y1,x2,y2 = int(input()), int(input()), int(input()), int(input())
# Cálculo das diferenças
dx = abs(x2 - x1)
dy = abs(y2 - y1)

# 1. Distância Euclidiana (L2)
dist_euclidiana = (dx**2 + dy**2)**0.5

# 2. Distância City-block / Manhattan (L1)
dist_city_block = dx + dy

# 3. Distância Chessboard / Chebyshev (Linf)
dist_chessboard = max(dx, dy)

# Saída formatada conforme os casos de teste
print(f"{dist_euclidiana:.2f}")
print(f"{dist_city_block:.2f}")
print(f"{dist_chessboard:.2f}")
Writing EP01_01.py
# Espera que você digite 4 números inteiros ao executar esta célula.
# No Jupyter ou Google Colab, a mágica %run -i permite que o script leia do teclado.
# No terminal comum, você usaria: python3 EP01_01.py (sem o '!' e sem '%run').

# %run -i EP01_01.py
# Envia 4 inteiros como entrada padrão (stdin) para o script EP01_01.py usando um pipe
!echo -e "0\n0\n4\n4" | python3 EP01_01.py
5.66
8.00
4.00
TestSuite("EP01_01.py").run()
✔️ EP01_01.cases já existe em casos/
📋 5 caso(s) carregado(s) de casos/EP01_01.cases

🔍 Testando Python: EP01_01.py
✔️ Caso 1: OK
✔️ Caso 2: OK
✔️ Caso 3: OK
✔️ Caso 4: OK
✔️ Caso 5: OK

📊 Resultado: 5/5 (100.0%)
🎉 Parabéns! Todos os testes passaram.