Kandangin Kambing pake Convex Hull (2)

Oke, setelah pada postingan kemarin sempat php (pemberi harapan palsu), kali ini akan saya kupas algoritma penyelesaian problem convex hull dengan pendekatan metode brute-force, berguna banget nih supaya kambing-kambing agan tidak lepas, monggo dinikmati...

Gagasan Awal

Ingat dengan apa yang dikatakan dosen saya pada postingan sebelumnya, bahwa

"dua titik yang membentuk garis dan menjadikan semua titik sisa berada di salah satu sisi garis, adalah titik-titik kandidat convex hull"

 adalah ide awal kita disini. Berikut ini ilustrasi tentang hal itu

titik (2,6) dan (8,7) adalah titik himpunan convex hull, karena semua titik sisa berada pada salah satu sisi dari garis tersebut. Begitu juga dengan titik (2,6) dan (1,3) adalah titik himpunan convex hull karena semua titik sisa terletak di salah satu sisi dari garis yang mereka bentuk. Lha terus gimana bos caranya kita tau kalo semua titik nimbrung di salah satu sisi garis? Kita flashback ke zaman SMA, persamaan garis berguna banget tuh untuk nylesein masalah ini.

Kanan atau Kiri yah?

Maksudnya gimana bos? Gini, let's say titik A adalah (2,6), titik B adalah (8,7) dan titik C adalah (7,4). Ke arah mana supaya garis AB mendekat ke garis AC? Kanan atau kiri? Begitu. Eh, ternyata si garis AB ke milih jalur kanan, yaudah kanan. Kalau memang garis titik A dan B adalah himpunan convex hull, garis AB harus ke arah kanan terus dong untuk mendekati semua garis yang dibentuk titik A dengan titik sisa? Mudeng?

Gambar ini mungkin bisa membantu teman-teman dalam mendapatkan arah yang harus dituju suatu garis,

Apa saya bilang, pelajaran SMA kembali membantu kita kan? Kita main-main dengan gradien di sini. Gradien yang lebih besar otomatis membentuk sudut yang lebih besar dengan titik acuan. Pada gambar di atas, gradien (baca: kemiringan) garis AB terhadap garis x = 7 lebih besar daripada kemiringan garis AC. Oleh karena itu titik C ada di sebelah kanan (baca dari bawah ke atas) dari garis AB. Berikut ini source code untuk menentukan posisi titik,

int side (dot a, dot b, dot c)
{
    int dx1 = b.x - a.x;
    int dx2 = c.x - a.x;
    int dy1 = b.y - a.y;
    int dy2 = c.y - a.y;
    if (dx1 * dy2 > dy1 * dx2)
        return -1;
    if (dx1 * dy2 < dy1 * dx2)
        return 1;
    return 0;
}

Finally...

Kita akan mengulangi langkah yang telah kita lakukan sebelumnya untuk semua titik, sehingga bisa didapatkan, running time dari algoritma ini adalah O(n³), karena untuk setiap titik yang membentuk kurva harus berhubungan dengan 2 titik lainnya dan sekalinya sudah terbentuk garis dugaan sementara, harus diperiksa, apakah semua titik yang tersisa terletak pada sisi yang sama atau tidak, berikut ini adalah hasil implementasi penyelesaian dalam bentuk code,

#include "stdio.h"
#include "math.h"
#include "string.h"

int n = 6;
typedef struct a
{
    int x, y;
} dot;

int side (dot a, dot b, dot c)
{
    int dx1 = b.x - a.x;
    int dx2 = c.x - a.x;
    int dy1 = b.y - a.y;
    int dy2 = c.y - a.y;
    if (dx1 * dy2 > dy1 * dx2)
        return -1;
    if (dx1 * dy2 < dy1 * dx2)
        return 1;
    return 0;
}

int main()
{
    dot a[n];
    for (int i = 0; i < n; i++)
        scanf ("%d %d", &a[i].x, &a[i].y);
    bool flag[n];
    memset (flag, false, n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int sisa = 0;
            if (i != j)
            {
                for (int k = 0; k < n; k++)
                    if (side (a[i], a[j], a[k]) == 1)
                        sisa++;
                if (sisa == 0 || sisa == n - 2)
                    flag[i] = flag[j] = true;
            }
        }
    }
    printf ("ans :\n");
    for (int i = 0; i < n; i++)
        if (flag[i])
            printf ("%d %d\n", a[i].x, a[i].y);
}

Silahkan dipelajari, masih ada kekurangan di bagian outputnya. Output belum tercetak secara teratur, seharusnya output ditulis dalam urutan searah jarum jam atau berlawanan arah jarum jam. Dari segi optimasi code, masih ada beberapa yang temen-temen bisa perbaiki. Baik, sekarang tiba di penghujung posting, semoga apa yang saya tulis bermanfaat. Terima kasih sudah mau mampir di blog ane, semoga kambing-kambing kita tidak lepas ya bro, sayonara...

Continue

Kandangin Kambing pake Convex Hull

Convex Hull adalah permasalahan di mana kita diminta untuk membentuk suatu curva yang mampu mengcover semua himpunan titik dengan jumlah garis yang paling minimal. Gini gini, misalkan ada kawanan kambing bebas di padang rumput, nah dengan menyebutnya sebagai permasalah convex hull,

Continue

100 - The 3n + 1 problem

Kali ini saya akan membahas soal UVA yang berjudul "The 3n + 1", untuk soal selengkapnya bisa dilihat di sini. Ada sebuah istilah "loop cycle" yang didefinisikan sebagai berikut :

input n
print n
selama n != 1
    jika n ganjil maka n = 3 * n + 1
    jika n ganjil maka n = n / 2
    print n

Jika program tersebut dieksekusi, untuk n = 5, maka akan tercetak angka 5, 16, 8, 4, 2, 1. Artinya untuk n = 5 terdapat 6 iterasi, ya kan? Nah, dalam soal diatas, kita diminta untuk mendapatkan nilai iterasi maksimal dari rentang suatu bilangan, yah let's say bilangannya adalah i dan j. Nah bagaimana cara agan untuk mendapatkannya? Sebenarnya ada banyak pendekatan sih. Mungkin bisa kita mulai dengan algo primitif seperti di bawah ini untuk mendapatkan jumlah "loop cycle" dari masing-masing bilangan :

while (temp > 1)
{
    if (temp % 2 != 0)
        temp = 3 * temp + 1;
    else
        temp = temp >> 1;
    c++;
}

Namun, ada sesuatu yang bisa kita mainkan di sini. Apa yah? Ya, lihat di bagian kondisional ketika temp ganjil. Ganjil x ganjil + 1 jadi bilangan apa hayo? Yup, betul, jadi genap. Terus ngapain bos? Kita bisa rangkap 2 statemen sekaligus dalam sekali loop ketika nilai temp ganjil, masuk? Jadi syntaksnya akan jadi seperti ini,

while (temp > 1)
{
    if (temp & 1)
    {
        temp = 3 * temp + 1;
        temp = temp >> 1;
        c+=2;
    }
    else
    {
        temp = temp >> 1;
        c++;
    }
}

perintah di atas sudah dimodifikasi dengan mengganti operator aritmatika (+,-,x,/) dengan operator bitwise, karena operator bitwise ini memiliki waktu eksekusi yang lebih cepat dari operator aritmatik biasa, temp = temp >> 1, artinya temp dibagi 2, karena bit paling kiri dibuang sebanyak satu bit, sedangkan untuk memeriksa bilangannya ganjil atau genap cukup dengan operator and (&), maksudnya jika bilangan ganjil (bit paling kiri bernilai 1 dalam representasi biner) di "and" kan dengan 1 pasti hasilnya satu kan? Makanya ini bisa digunakan untuk mendeteksi sebuah bilangan ganjil atau genap.

Yup, untuk masalah cycle loop beres lah. Dalam soal tersebut, kita diminta untuk menerima inputan selama file input masih ada, apa maksudnya gan? Kita diminta untuk menerima inputan selama kondisi EOF (end of file -> kondisi dimana scanf bernilai false) belum ditemui. Jangan lupa, bahwa program ini juga menerima input terbalik, artinya 1 10000 dengan 10000 1 dianggap sama. Oleh karena itu harus ada pengecekan setelah input. Eits, ada yang lupa, kita kan diminta untuk mendapatkan nilai terbesar dari loop cycle, ya kan? maka dari itu, setelah kita dapatkan nilai loop cycle dari setiap bilangan dalam rentang, selalu periksa loop cycle yang didapat sekarang dengan loop cycle yang didapat sebelumnya, lebih besar atau lebih kecil. So, panjang lebar ngomong dari atas ke bawah ternyata cuma untuk kodingan sependek ini, ladies and gentleman, i give you, 3n + 1 solution, here it is

#include "stdio.h"
int main()
{
    long long int a, b, x, y, i, maks, c, temp;
    while (scanf("%lld %lld", &a, &b) != EOF)
    {
        maks = 0;
        if (a < b)
        {
            x = a;
            y = b;
        }
        else
        {
            x = b;
            y = a;
        }
        for (i = x; i <= y; i++)
        {
            temp = i;
            c = 1;
            while (temp > 1)
            {
                if (temp & 1)
                {
                    temp = 3 * temp + 1;
                    temp = temp >> 1;
                    c+=2;
                }
                else
                {
                    temp = temp >> 1;
                    c++;
                }
            }
            if (c > maks)
                maks = c;
        }
        printf("%lld %lld %lld\n", a, b, maks);
    }
}

Nah, sampai kita pada akhir post, semoga bermanfaat, terus belajar, dan mohon maaf jika ane berbuat salah. Salam Coding...:)

Continue