Mbiri-biri program Domba dan Jalur Serigala dengan ADT garis dan ADT point

Latihan membuat instruksi pembelajaran Mbiri-biri program domba dan jalur serigala dengan menggunakan ADT garis dan ADT point, diimplementasikan dengan bahasa pemrograman Rust.

Pembaca akan mempelajari bagaimana memodelkan masalah geometri sederhana (jarak titik ke garis) dengan ADT Point dan ADT Garis di Rust, serta menerapkan alur pembacaan input, validasi sederhana, perhitungan jarak, dan penghitungan jumlah titik yang memenuhi kondisi.

Tujuan Pembelajaran

Setelah menyelesaikan tugas ini, peserta mampu:

1. Menjelaskan hubungan antara ADT Point dan ADT Garis untuk menyelesaikan masalah jarak geometri.

2. Mengimplementasikan Point dan Garis sebagai modul Rust yang terpisah (file point.rs dan garis.rs).

3. Menghitung jarak terpendek dari titik ke garis (formulasi matematika dan implementasi numerik).

4. Menangani kasus garis degenerate (titik awal == titik akhir) dengan benar.

5. Membaca input sesuai spesifikasi dan menampilkan jumlah domba yang dalam bahaya (d <= b).

Prasyarat

• Pemahaman dasar Rust: struct, impl, mod, use, fn main().

• Mengetahui cara membaca input sederhana (std::io) dan parsing angka.

• Pemahaman dasar tentang bilangan riil (float) dan operasi aritmetika.

Persyaratan Input / Output

Program membaca dari stdin angka-angka yang dipisah spasi/enter:

1. Nilai b (jarak ambang, bisa integer atau float).

2. Dua point untuk mendefinisikan garis: x1 y1 lalu x2 y2. (Koordinat bilangan, bisa integer atau float.)

3. Nilai n (jumlah titik/domba).

4. Diikuti n baris (atau token) yang masing-masing berisi xi yi (koordinat tiap domba).

Program menuliskan satu angka: jumlah domba dengan jarak d <= b dari garis.

Ide Penyelesaian secara singkat

• Baca b, dua titik Pawal(x1,y1) dan Pakhir(x2,y2). Bentuk Garis.

• Untuk setiap titik domba Pi(xi,yi): hitung jarak terpendek d dari Pi ke garis.

  • Jika garis degenerate (Pawal == PAkhir), gunakan jarak Euclidean Pi ke Pawal.

  • Jika tidak, gunakan rumus jarak titik-ke-garis:

\( d = \frac{|(x_2-x_1)(y_1-y_i) - (x_1-x_i)(y_2-y_1)|}{\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}}\)

• Tampilkan total domba yang dalam bahaya.

Modul & Kode

Buat project baru cargo new mbiribiri lalu letakkan file berikut.

src/point.rs — ADT Point (sederhana)

// src/point.rs
// ADT Point: tipe data sederhana untuk titik 2D.
// Ditulis agar mudah dibaca pemula.

#[derive(Debug, Clone, Copy)]
pub struct Point {
    pub x: f64,
    pub y: f64,
}

impl Point {
    /// Konstruktor
    pub fn new(x: f64, y: f64) -> Self {
        Point { x, y }
    }

    /// Jarak Euclidean ke titik lain
    pub fn distance_to(&self, other: &Point) -> f64 {
        let dx = self.x - other.x;
        let dy = self.y - other.y;
        (dx*dx + dy*dy).sqrt()
    }
}

Komentar singkat: field x dan y dibuat pub untuk memudahkan akses di modul lain; jika ingin enkapsulasi penuh, bisa dibuat private dan sediakan getter.

src/garis.rs — ADT Garis

// src/garis.rs
// ADT Garis: representasi garis yang dibentuk dari dua titik (Pawal, Pakhir).
// Menyediakan fungsi jarak terpendek titik ke garis.

use crate::point::Point;

#[derive(Debug, Clone, Copy)]
pub struct Garis {
    pub p1: Point,
    pub p2: Point,
}

impl Garis {
    /// Konstruktor
    pub fn new(p1: Point, p2: Point) -> Self {
        Garis { p1, p2 }
    }

    /// Jarak terpendek dari titik p ke garis yang dibentuk p1-p2.
    /// Jika p1 == p2 (garis degenerate), kembalikan jarak Euclidean p ke p1.
    pub fn distance_to_point(&self, p: &Point) -> f64 {
        let x1 = self.p1.x;
        let y1 = self.p1.y;
        let x2 = self.p2.x;
        let y2 = self.p2.y;
        let xi = p.x;
        let yi = p.y;

        let dx = x2 - x1;
        let dy = y2 - y1;
        let denom = (dx*dx + dy*dy).sqrt();

        // Jika denom == 0, Pawal == PAkhir: fallback ke jarak titik ke p1
        if denom == 0.0 {
            return p.distance_to(&self.p1);
        }

        // Numerator: absolute value of cross product (area * 2)
        let num = (dx*(y1 - yi) - (x1 - xi)*dy).abs();

        num / denom
    }
}

Komentar: rumus diimplementasikan langsung dari formula jarak titik-ke-garis. Fungsi mengembalikan f64.

src/main.rs — Driver: baca input, hitung, tampilkan

// src/main.rs
mod point;
mod garis;

use std::io::{self, Read};
use point::Point;
use garis::Garis;

fn main() {
    // Baca seluruh stdin sebagai string, kemudian parse whitespace-separated tokens
    let mut input = String::new();
    if io::stdin().read_to_string(&mut input).is_err() {
        eprintln!("Gagal membaca input.");
        return;
    }

    // Split dan parse menjadi iterator f64
    let mut iter = input
        .split_whitespace()
        .filter(|s| !s.is_empty())
        .map(|s| s.parse::<f64>());

    // Helper closure untuk membaca next f64, dengan error handling sederhana
    let mut next_num = || -> Option<f64> {
        while let Some(res) = iter.next() {
            match res {
                Ok(v) => return Some(v),
                Err(_) => {
                    // jika parsing gagal, coba terus ke token berikutnya
                    continue;
                }
            }
        }
        None
    };

    // Baca b
    let b = match next_num() {
        Some(v) => v,
        None => { eprintln!("Input tidak lengkap: b"); return; }
    };

    // Baca dua point untuk garis: x1 y1 x2 y2
    let x1 = next_num().unwrap_or_else(|| { eprintln!("Input tidak lengkap: x1"); 0.0 });
    let y1 = next_num().unwrap_or_else(|| { eprintln!("Input tidak lengkap: y1"); 0.0 });
    let x2 = next_num().unwrap_or_else(|| { eprintln!("Input tidak lengkap: x2"); 0.0 });
    let y2 = next_num().unwrap_or_else(|| { eprintln!("Input tidak lengkap: y2"); 0.0 });

    let garis = Garis::new(Point::new(x1, y1), Point::new(x2, y2));

    // Baca n
    let n_f = match next_num() {
        Some(v) => v,
        None => { eprintln!("Input tidak lengkap: n"); return; }
    };
    let n = n_f as usize;

    let mut count = 0usize;
    let eps = 1e-9_f64;

    for i in 0..n {
        let xi = match next_num() {
            Some(v) => v,
            None => { eprintln!("Input tidak lengkap: xi at index {}", i); break; }
        };
        let yi = match next_num() {
            Some(v) => v,
            None => { eprintln!("Input tidak lengkap: yi at index {}", i); break; }
        };
        let p = Point::new(xi, yi);
        let d = garis.distance_to_point(&p);
        // bandingkan dengan b, dengan sedikit toleransi numerik
        if d <= b + eps {
            count += 1;
        }
    }

    println!("{}", count);
}

Catatan implementasi utama:

• Input dibaca sekali penuh dan diparsing token demi token menjadi f64. Ini sederhana untuk format input whitespace-separated.

• Perbandingan d <= b + eps dipakai untuk mengurangi masalah pembulatan floating point kecil.

• Jika garis degenerate (dua titik pembentuk sama), fungsi distance_to_point mengembalikan jarak Euclidean ke titik pembentuk.

Contoh Input / Output

Contoh dari soal (disesuaikan format whitespace):

Input:

5
1 2
3 4
2
1 1
2 2

Penjelasan:

• b = 5

• garis melalui (1,2) dan (3,4)

• n = 2

• titik (1,1) dan (2,2)

Output (jumlah domba dalam jarak <= 5):

2

(Contoh ini sesuai ilustrasi pada gambar: kedua titik berada dekat dengan garis.)

Penjelasan Matematika untuk pemula

• Garis lewat titik P1(x1,y1) dan P2(x2,y2) dapat dilihat sebagai vektor arah (dx, dy) = (x2-x1, y2-y1).

• Jarak perpendicular titik P(xi,yi) ke garis dapat dihitung dengan luas segitiga yang dibentuk oleh P1, P2, P: luas = 0.5 * |(cross product)|; jarak = (2 * luas) / panjang(basis) → sama dengan formula yang dipakai.

• Jika dx = dy = 0 (P1==P2), garis tak terdefinisi; kita gunakan jarak titik ke P1 (jarak Euclidean).

Edge Cases yang harus diajarkan dan diuji

1. Garis degenerate (Pawal == PAkhir): gunakan jarak Euclidean ke titik itu.

2. Semua titik bilangan integer besar / kecil: gunakan f64 agar aman numeriknya.

3. b sangat kecil (0): hanya titik yang tepat berada di garis (jarak ≈ 0) akan dihitung — perhatikan toleransi eps.

4. Nilai input tidak lengkap / parsing gagal: implementasi sederhana melaporkan error dan keluar. Untuk tugas lanjutan, buat validasi lebih baik.

5. Precision floating point: untuk kasus sangat sensitif, gunakan toleransi (eps = 1e-9) atau logika integer rational jika semua input integer (lebih advanced).

6. n = 0: program menampilkan 0. (Skrip di atas mengasumsikan n >= 0.)

Aktivitas Latihan (untuk pembelajaran)

1. Ubah program agar menerima koordinat sebagai i64 (integer) dan melakukan perhitungan jarak menggunakan rational arithmetic (tanpa sqrt) untuk menentukan apakah d <= b dengan cara membandingkan kuadrat — tantangan ini untuk yang ingin belajar numerik lebih lanjut.

2. Tambahkan output listing indeks domba yang terancam (nomor 1..n) selain jumlahnya.

3. Visualisasikan titik dan garis dengan plotting sederhana (mis. export ke CSV lalu buka di spreadsheet).

Pertanyaan Refleksi dengan jawaban singkat/clue

1. Mengapa kita memilih f64 untuk koordinat ketimbang f32? Clue: f64 memberikan presisi lebih besar sehingga lebih aman untuk perhitungan jarak. Jawaban singkat: f64 mengurangi risiko error pembulatan pada perhitungan geometri.

2. Apa yang terjadi bila Pawal == PAkhir? Clue: garis tidak punya arah; gunakan jarak Euclidean ke titik pusat sebagai definisi jarak. Jawaban singkat: kita hitung jarak titik ke titik tunggal tersebut.

3. Mengapa ada eps saat membandingkan d <= b? Clue: floating point tidak selalu presisi sempurna; gunakan sedikit toleransi untuk mengakomodasi rounding. Jawaban singkat: untuk tidak kehilangan titik yang seharusnya sama jaraknya akibat pembulatan.

4. Bagaimana jika semua nilai input integer sehingga bisa dibandingkan persis? Clue: Anda bisa membandingkan kuadrat jarak atau memakai formula cross product dalam bentuk integer (lebih advanced). Jawaban singkat: perbandingan integer menghindari isu floating point, tapi implementasinya lebih rumit.

Referensi

• Materi ADT Point / Garis (sebagai acuan pengajaran) diadaptasi dari: Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung — Materi Struktur Data & ADT (contoh penggunaan ADT Point & Garis).

• Rumus jarak titik-ke-garis: materi geometri dasar (buku atau sumber online matematika elementer).