UVa 12240 - Cocircular Points

Berhubung baru kuliah komputasional geometri, kali ini saya akan membahas soal geometri UVa 12240 - Cocircular Points.

Inti soal ini sederhana: diberikan N buah titik. Cari himpunan titik dengan anggota sebanyak mungkin yang saling cocircular. Sebuah himpunan titik dinyatakan saling cocircular apabila ada lingkaran sedemikian sehingga seluruh titik di himpunan itu terletak pada sisi lingkaran tersebut.

Observasi:
Dari tiga buah titik yang tidak segaris, kita bisa membuat tepat sebuah lingkaran yang sisinya menyentuh ketiga titik tersebut. Titik pusat segitiga (sebut saja di $(P_x, P_y)$)itu dapat dicari dengan menyelesaikan persamaan berikut:

$\begin{eqnarray*}r^2 &=& (A_x-P_x)^2+(A_y-P_y)^2 \\ r^2 &=& (B_x-P_x)^2+(B_y-P_y)^2 \\ r^2 &=& (C_x-P_x)^2+(C_y-P_y)^2 \end{eqnarray*}$

UVa 1232 - Skyline

Soal ini bersumber dari ICPC Regional Asia, Singapore, 2007-2008. Menarik untuk dibahas, sehingga saya menuliskannya di sini. Sangat disarankan Anda mencoba terlebih dahulu untuk menyelesaikannya.

Inti soalnya kita memiliki sebuah array yang awalnya berisi angka 0 dan akan melayani sejumlah operasi. Operasi ini adalah membuat nilai array di suatu interval tertentu menjadi nilai maksimum antara nilai sebelumnya dengan suatu nilai yang baru. Tugas kita adalah menghitung ada berapa kali perubahan nilai yang terjadi.

Sebuah kata kunci yang tidak boleh Anda lewatkan adalah "You may assume that the amount of overlap for each dataset is at most 2000000". Biasanya soal yang menyebutkan batasan seperti ini dapat diselesaikan dengan algoritma output-sensitive, artinya kompleksitasnya bergantung pada keluaran.

Berhubung di soal ini hanya ada satu macam operasi (query), kita bisa mengerjakannya secara offline (setiap operasi dibaca dulu, lalu dikerjakan dulu semuanya, baru dicetak semuanya). Biasanya cara ini lebih mudah ketimbang kita harus melaksanakan setiap operasi secara online.

Tentang Pembuatan Soal Competitive Programming

Pada kesempatan kali ini, saya akan membagikan bagaimana cara pembuatan soal menurut pengalaman-pengalaman yang saya saksikan atau saya alami sendiri. Karena pengalaman itu tidak saya dokumentasikan, saya tidak bisa menyebutkan sumbernya satu per satu. Orang yang mungkin terlibat dalam tulisan ini adalah Ashar, Brian, Chris, Felix, Karol, Suhendry, Reinhart, atau Risan.

Perlu diperhatikan bahwa tulisan ini tidak menyatakan hal yang wajib Anda lakukan, karena tulisan ini hanya didasarkan pada pengalaman pribadi saya.

Fokus utama dari tulisan ini adalah jenis soal batch. Bila Anda belum tahu apa itu soal batch, coba perhatikan jenis-jenis soal berikut:

1. Batch: diberikan berkas masukan yang sifatnya rahasia, rancang algoritma sehingga menghasilkan keluaran seperti yang diinginkan soal. Algoritma harus memenuhi batasan tertentu seperti batas waktu dan memori.
2. Interactive: rancang algoritma untuk berinteraksi dengan program grader untuk suatu tujuan tertentu. Misalnya tebak angka, bermain game, atau adu strategi.
3. Output only: diberikan berkas masukan. Rancang algoritma untuk menghasilkan keluaran seperti yang diinginkan soal. Yang kita kumpulkan adalah berkas keluaran yang dihasilkan. Bedanya dengan batch adalah sifat testcase yang tidak rahasia dan tidak ada batasan waktu atau memori (karena yang dikumpulkan adalah berkas keluarannya).

UVa 12589 - Learning Vector

Soal yang akan dibahas kali ini adalah UVa 12589 - Learning Vector. Singkatnya, kita berikan N vektor. Pilih K vektor sedemikian sehingga bila vektor-vektor itu digambar dalam poligon dengan urutan tertentu, akan menghasilkan luas daerah di atas sumbu-x terbesar.

Observasi 1:
Misalkan kita memiliki sejumlah vektor. Menggambarkannya dalam bentuk poligon dengan urutan apapun akan berakhir di suatu titik yang sama. Alasannya karena penjumlahan vektor bersifat komutatif. Permasalahan berikutnya adalah bagaimana kita menentukan urutan penggambarannya sehingga luas yang dihasilkan maksimal.

Observasi 2:
Untuk menghasilkan luas di atas sumbu-x maksimal, sejumlah vektor itu harus kita urutkan mulai dari yang "gradien"-nya terbesar. Jadi muncul strategi greedy untuk mengurutkan vektor-vektor tersebut.