tokilearning - Webs

Update 2017-06-14:
Web tokilearning yang lama sudah tidak aktif, Anda sudah tidak bisa mengumpulkan jawaban untuk soal ini. Namun Anda masih dapat mempelajarinya di tulisan ini.

Oke kali ini saya akan membahas soal Webs dari tokilearning. Konon katanya soal ini digunakan untuk simulasi Pelatnas 2 TOKI 2010 di UGM. Dari gaya bahasanya, kelihatannya soal ini dibuat oleh Irvan Jahja. Sekilas, soal ini tampak menyeramkan. Pada kenyataannya tidak terlalu menyeramkan, asal kita memilah-milah dan tahu apa yang harus dikerjakan.

Tugas kita adalah menghitung berapa banyak segitiga yang ada!

Biasanya, soal geometri seperti ini erat hubungannya dengan graf. Hmm coba perhatikan, seandainya titik perpotongan dari dua benang kita anggap sebagai node, lalu benang yang menghubungkan antar dua titik perpotongan sebagai edge, maka kita dapatkan sebuah graf yang planar.

Berapa banyak node maksimumnya? Persoalan berapa banyaknya node ini serupa dengan persoalan berikut:

Diberikan sebuah kue berbentuk persegi. Dengan N kali pemotongan, berapa banyaknya potongan maksimum yang bisa dihasilkan?

Jawab:
Misalkan sudah dilakukan X-1 kali pemotongan di kue tersebut dan banyaknya potongan yang dihasilkan sejauh ini adalah optimal (sebanyak mungkin). Jika kita memotong sekali lagi, kita pasti bisa memotong dengan melewati setiap garis potongan yang pernah dilakukan sebelumnya. Karena kita melewati X-1 bekas pemotongan, kita menghasilkan X buah potongan yang baru.
Dari observasi tersebut, kita dapat merancang rumus rekursif untuk jawaban atas pertanyaan di atas. Misalkan f(x) menyatakan banyaknya potongan kue maksimum jika dilakukan x kali pemotongan. Didapat:
\(f(0) = 1\), hanya ada 1 potong kue jika tidak dilakukan pemotongan sama sekali
\(f(x) = f(x-1) + x\)
Dalam bentuk bukan rekursif:
\(f(x) = 1 + 1 + 2 + 3 + ... + x\)
atau
\(f(x) = 1 + \frac{x(x+1)}{2}\)
Sehingga banyaknya node maksimalnya adalah \(O(N^2)\)

Sekarang kita kembali lagi ke soal. Kapan 3 buah node (sebut saja u, v, dan w) menjadi sebuah segitiga sesuai yang diinginkan soal? Hal ini terjadi jika terdapat edge yang menghubungkan (u, v), (u, w), dan (v, w). Jadi kita tinggal pilih suatu node, lalu cek untuk setiap pasangan tetangganya apakah mereka terhubung. Jika ya, tambahkan jawaban akhir dengan 1. Di akhir, bagi jawaban dengan 3 karena satu segitiga akan dihitung 3 kali. Berhubung suatu titik tidak mungkin menjadi titik persekutuan dari 3 atau lebih garis, maka setiap node hanya akan memiliki maksimal 4 tetangga. Jadi jika grafnya sudah dibangun, menghitung banyaknya segitiga dapat dilakukan dalam \(O(N^2)\)

Sekarang masalahnya tinggal bagaimana cara membangun graf tersebut. Pastinya anda membutuhkan cara untuk mencari titik potong sepasang segmen garis. Selain itu, anda juga mungkin membutuhkan cara untuk memeriksa apakah suatu titik berapa di suatu segmen garis. Segala yang dibutuhkan untuk menjawab pertanyaan tersebut adalah ilmu tentang vektor dalam geometri, terutama cross product. Saya tidak membahas bagaimana cara mencari titik potong antar segmen garis atau memeriksa titik ada di suatu garis. Anda harus mencari tahu sendiri.

Membangun graf dari masukan yang diberikan dapat dilakukan dalam \(O(N^2)\), sehingga kompleksitas solusi adalah \(O(N^2)\). Cukup untuk mendapatkan accepted. Berikut kode saya: