Jumat, 19 April 2013

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*}\)

Detilnya tidak saya tuliskan, tetapi persamaan itu pada akhirnya akan menghasilkan sistem persamaan linier 2 variabel \((P_x, P_y)\). Cara yang mudah diimplementasikan untuk menyelesaikan persamaan itu adalah dengan invers matriks (matriksnya hanya 2*2).

Dengan begitu, muncul ide brute force dimana kita memilih 3 titik, membuat sebuah lingkaran, lalu mencari banyaknya titik yang menyentuh sisi lingkaran itu. Sayangnya solusi ini memiliki kompleksitas \(O(N^4)\), tidak cukup cepat untuk menyelesaikan soal ini.

Berhubung nilai N maksimal 100, algoritma yang kita butuhkan harus lebih baik dari \(O(N^4)\). Ketimbang memilih 3 titik lalu membuat lingkaran yang sudah membutuhkan \(O(N^3)\), mari kita coba dengan hanya memilih 2 titik saja. Bila hanya ada 2 titik, kita bisa membuat tak hingga banyaknya lingkaran. Meskipun begitu, setiap lingkaran yang terbentuk memiliki lokasi titik pusat yang unik.


Bila titik berwarna biru menyatakan 2 titik yang kita pilih, akan muncul sejumlah titik pusat lingkaran. Bila ada X titik pusat yang tumpang tindih, artinya lingkaran yang berpusat di sana dapat cocircular dengan 2+X titik. Dengan begitu untuk setiap 2 titik yang kita pilih, kita dapat mengenumerasi seluruh titik pusat lingkaran yang terbentuk, lalu menghitung banyaknya titik pusat tumpang tindih yang paling maksimum. Enumerasi dapat dilakukan dalam \(O(N)\) dan perhitungan dapat dilakukan dalam \(O(1)\) atau \(O(\log{N})\) dengan direct addressing table (array 2 dimensi atau STL map), sehingga secara teoritis kompleksitasnya \(O(N^3)\).

Sayangnya, ternyata agak sulit karena titik pusat bisa saja berbentuk pecahan. Oleh karena itu alternatifnya kita dapat mengurutkan daftar titik pusat itu, lalu lakukan linear scan untuk menghitung banyaknya elemen yang sama. Kompleksitas akhir solusi adalah \(O(N^3 \log{N})\). Berikut ini implementasi saya:

1 komentar :