Soal ini saya hadapi pada saat latihan Pelatnas 2 TOKI 2011. Saya benar-benar tidak bisa mengerjakannya pada saat itu. Akhirnya saya kembali pada saat Pelatnas 4 TOKI 2011, dan berhasil membalas dendam dengan menyelesaikan soal ini >:-)
Dari deskripsi soalnya, terlihat bahwa soal ini cukup sederhana: diberikan sebuah poligon yang mungkin tidak konveks dan sejumlah titik. Tentukan banyaknya titik yang ada di dalam poligon!
Memeriksa apakah suatu titik berada di dalam poligon bisa dilakukan dengan algoritma ray casting, yaitu dengan membuat segmen garis imajiner dari titik tersebut ke suatu arah sembarang, lalu hitung berapa kali garis itu berpotongan dengan poligon. Bila genap, artinya titik berada di luar poligon dan bila ganjil, artinya titik berada di dalam poligon (tidak percaya? Cobalah!). Sayangnya algoritma ini agak repot dilakukan karena garis imajiner yang dibuat tidak boleh menyentuh titik sudut pada poligon. Lagipula kompleksitas untuk sekali pemeriksaan adalah O(N), padahal poligon yang diberikan bisa memiliki sisi sebanyak 100.000, dan banyaknya titik juga bisa sampai 100.000.
Bila tidak ada properti khusus pada soal ini, maka sepertinya soal ini mustahil untuk diselesaikan. Beruntungnya, ada sebuah kalimat yang sangat penting pada soal: "Exhausted, he moves to a place within the pen from which he can see the whole interior of the pen (without any fence getting in the way) and begins to count the sheep which are within it."
Artinya, dijamin ada sebuah titik yang mana bila seseorang berdiri di sana, dia bisa melihat seluruh isi poligon (kemudian diberitahu bahwa titik tersebut ada di (0,0)). Berikut ini gambar yang memberi ilustrasi jenis poligon tersebut. Poligon di sebelah kiri merupakan poligon yang valid, dan yang kanan tidak karena daerah yang berwarna coklat tidak bisa dilihat:
Tentunya, tidak ada poligon yang tidak valid pada masukan.
Lalu apa yang bisa kita lakukan? Coba tarik garis dari titik (0,0) ke setiap titik sudut poligon, lalu perhatikan apa yang bisa dilakukan:
Ternyata, setiap titik berasosiasi dengan sebuah daerah! Pada setiap daerah, terdapat sebuah segitiga yang merupakan bagian dari poligon. Oleh karena itu, memeriksa ada di dalam atau tidaknya titik bisa dilakukan dengan memeriksa apakah titik itu ada di dalam segitiga daerahnya. Memeriksa apakah titik ada di dalam segitiga dapat dilakukan dalam O(1) dengan operasi cross product.
Sekarang tugas kita adalah menemukan bagaimana menemukan daerah yang berasosiasi dengan sebuah titik. Terdapat setidaknya dua cara, yaitu dengan sorting + binary search, atau dengan sorting + line sweep. Pengurutan dilakukan berdasarkan sudut. Dengan cara binary search, tinggal cari daerah yang sudut batas-batasnya melingkupi sudut titik tersebut dalam O(log N) (sudut di sini mengacu pada sudut yang dibentuk pada sumbu-x bagian positif). Sedangkan dengan line sweep, caranya seperti ada dua variabel penunjuk yang terus bergerak maju. Penunjuk pertama mengacu pada titik, dan penunjuk kedua mengacu pada daerah. Selagi titik yang ditunjuk berada di dalam daerah yang ditunjuk penunjuk kedua, geser terus penunjuk pertama. Bila tidak, baru geser penunjuk kedua. Contoh solusi yang saya berikan menggunakan pendekatan line sweep.
Setelah diketahui daerah setiap titik, tinggal diperiksa saja lokasinya terhadap segitiga. Kompleksitas keseluruhan menjadi O(N log N). Selesaikah? Belum!
Pada persoalan geometri, penting bahwa Anda harus memperhatikan kemungkinan terjadi kasus degenerate. Apalagi untuk soal yang melibatkan poligon tidak konveks, peluang adanya kasus degenerate yang dapat merusak jalannya algoritma sangat besar. Perhatikan contoh berikut:
Pada kasus di sebelah kiri, "segitiga" pada "daerah" yang diberi tanda lumpuh menjadi sebuah garis. Hal ini bisa menjadi lebih ekstrim seperti yang ditunjukkan pada dua gambar di sebelah kanannya. Saya sendiri menghadapi beberapa WA karena masalah ini.
Saya menyarankan Anda untuk mencoba mengerjakan soal ini, karena akan membantu dalam belajar implementasi algoritma geometri. Bila sudah "kepepet", Anda bisa melihat solusi saya sebagai referensi:
Dari deskripsi soalnya, terlihat bahwa soal ini cukup sederhana: diberikan sebuah poligon yang mungkin tidak konveks dan sejumlah titik. Tentukan banyaknya titik yang ada di dalam poligon!
Memeriksa apakah suatu titik berada di dalam poligon bisa dilakukan dengan algoritma ray casting, yaitu dengan membuat segmen garis imajiner dari titik tersebut ke suatu arah sembarang, lalu hitung berapa kali garis itu berpotongan dengan poligon. Bila genap, artinya titik berada di luar poligon dan bila ganjil, artinya titik berada di dalam poligon (tidak percaya? Cobalah!). Sayangnya algoritma ini agak repot dilakukan karena garis imajiner yang dibuat tidak boleh menyentuh titik sudut pada poligon. Lagipula kompleksitas untuk sekali pemeriksaan adalah O(N), padahal poligon yang diberikan bisa memiliki sisi sebanyak 100.000, dan banyaknya titik juga bisa sampai 100.000.
Bila tidak ada properti khusus pada soal ini, maka sepertinya soal ini mustahil untuk diselesaikan. Beruntungnya, ada sebuah kalimat yang sangat penting pada soal: "Exhausted, he moves to a place within the pen from which he can see the whole interior of the pen (without any fence getting in the way) and begins to count the sheep which are within it."
Artinya, dijamin ada sebuah titik yang mana bila seseorang berdiri di sana, dia bisa melihat seluruh isi poligon (kemudian diberitahu bahwa titik tersebut ada di (0,0)). Berikut ini gambar yang memberi ilustrasi jenis poligon tersebut. Poligon di sebelah kiri merupakan poligon yang valid, dan yang kanan tidak karena daerah yang berwarna coklat tidak bisa dilihat:
Tentunya, tidak ada poligon yang tidak valid pada masukan.
Lalu apa yang bisa kita lakukan? Coba tarik garis dari titik (0,0) ke setiap titik sudut poligon, lalu perhatikan apa yang bisa dilakukan:
Ternyata, setiap titik berasosiasi dengan sebuah daerah! Pada setiap daerah, terdapat sebuah segitiga yang merupakan bagian dari poligon. Oleh karena itu, memeriksa ada di dalam atau tidaknya titik bisa dilakukan dengan memeriksa apakah titik itu ada di dalam segitiga daerahnya. Memeriksa apakah titik ada di dalam segitiga dapat dilakukan dalam O(1) dengan operasi cross product.
Sekarang tugas kita adalah menemukan bagaimana menemukan daerah yang berasosiasi dengan sebuah titik. Terdapat setidaknya dua cara, yaitu dengan sorting + binary search, atau dengan sorting + line sweep. Pengurutan dilakukan berdasarkan sudut. Dengan cara binary search, tinggal cari daerah yang sudut batas-batasnya melingkupi sudut titik tersebut dalam O(log N) (sudut di sini mengacu pada sudut yang dibentuk pada sumbu-x bagian positif). Sedangkan dengan line sweep, caranya seperti ada dua variabel penunjuk yang terus bergerak maju. Penunjuk pertama mengacu pada titik, dan penunjuk kedua mengacu pada daerah. Selagi titik yang ditunjuk berada di dalam daerah yang ditunjuk penunjuk kedua, geser terus penunjuk pertama. Bila tidak, baru geser penunjuk kedua. Contoh solusi yang saya berikan menggunakan pendekatan line sweep.
Setelah diketahui daerah setiap titik, tinggal diperiksa saja lokasinya terhadap segitiga. Kompleksitas keseluruhan menjadi O(N log N). Selesaikah? Belum!
Pada persoalan geometri, penting bahwa Anda harus memperhatikan kemungkinan terjadi kasus degenerate. Apalagi untuk soal yang melibatkan poligon tidak konveks, peluang adanya kasus degenerate yang dapat merusak jalannya algoritma sangat besar. Perhatikan contoh berikut:
Pada kasus di sebelah kiri, "segitiga" pada "daerah" yang diberi tanda lumpuh menjadi sebuah garis. Hal ini bisa menjadi lebih ekstrim seperti yang ditunjukkan pada dua gambar di sebelah kanannya. Saya sendiri menghadapi beberapa WA karena masalah ini.
Saya menyarankan Anda untuk mencoba mengerjakan soal ini, karena akan membantu dalam belajar implementasi algoritma geometri. Bila sudah "kepepet", Anda bisa melihat solusi saya sebagai referensi:
Tidak ada komentar :
Posting Komentar