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:
syntax highlighting tutorial
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 | #include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>#include <string>#include <vector>#define REP(a,b) for (int a=0; a<b; a++)#define LL long long#define F first#define S second#define MP make_pair#define PB push_back#define PII pair<int,int> #define PLL pair<LL,LL> #define __ puts("")#define x F#define y Susing namespace std;PII tik[100002], grs[100002], pus;int ntik, ngrs, nkasus, tot, p, ori;bool ye;int area_sign(PII aa, PII bb, PII cc){ PLL a,b,c; a = MP(aa.F, aa.S); b = MP(bb.F, bb.S); c = MP(cc.F, cc.S); LL h = (a.x*b.y) + (b.x*c.y) + (c.x*a.y) - (a.x*c.y) - (b.x*a.y) - (c.x*b.y); if (h < 0){ return -1; }else if (h > 0){ return 1; }else{ return 0; }}inline int kuadran(PII a){ int ret; if ((a.x >= 0) && (a.y >= 0)){ ret = 1; }else if ((a.x <= 0) && (a.y >= 0)){ ret = 2; }else if ((a.x <= 0) && (a.y <= 0)){ ret = 3; }else if ((a.x >= 0) && (a.y <= 0)){ ret = 4; } return ret;}bool kom(PII a, PII b){ int kuada,kuadb; kuada = kuadran(a); kuadb = kuadran(b); if (kuada != kuadb){ return (kuada < kuadb); }else{ return (area_sign(pus,a,b) > 0); }}// true if t is clamped by a and bbool sec(PII t, PII a, PII b){ int h1,h2; h1 = area_sign(pus,a,t); h2 = area_sign(pus,b,t); if ((h1>=0) && (h2<=0)){ return 1; } return 0;}// true if t is inside triangle (pus, a, b)bool inside(PII t, PII a, PII b){ int h1,h2,h3; h1 = area_sign(pus,a,t); h2 = area_sign(a,b,t); h3 = area_sign(b,pus,t); if ((h1==0) && (h2==0) && (h3==0)){ // oh no! collinear! REP(k,2){ if ((a.x <= t.x) && (t.x <= b.x) &&(a.y <= t.y) && (t.y <= b.y)){ return 1; } swap(a,b); } return 0; }else if ((h1>=0) && (h2>=0) && (h3>=0)){ return 1; } return 0;}inline int succ(int a, int lim){ a++; if (a == lim) a = 0; return a;}inline int pred(int a, int lim){ a--; if (a < 0) a = lim-1; return a;}int main(){ // center of observation PII pus = MP(0,0); scanf("%d", &nkasus); REP(jt,nkasus){ scanf("%d%d", &ngrs, &ntik); REP(i,ngrs){ scanf("%d%d", &grs[i].x, &grs[i].y); // removes collinear if (i >= 2){ if (area_sign(grs[i-2], grs[i-1], grs[i]) == 0){ grs[i-1] = grs[i]; i--; ngrs--; } } } tot = 0; REP(i,ntik){ scanf("%d%d", &tik[i].x, &tik[i].y); // in origin? Count it and ignore if ((tik[i].x == 0) && (tik[i].y == 0)){ tot++; i--; ntik--; } } if (ntik > 0) sort(tik, tik+ntik, kom); grs[ngrs] = grs[0]; p = 0; REP(i,ntik){ while (!sec(tik[i], grs[p], grs[p+1])){ p = succ(p, ngrs); } ori = p; ye = 0; p = pred(p, ngrs); p = pred(p, ngrs); REP(k,5){ if (inside(tik[i], grs[p], grs[p+1])){ ye = 1; } p = succ(p, ngrs); if (ye) break; } p = ori; if (ye){ tot++; } } printf("%d\n", tot); } return 0; } |
Tidak ada komentar :
Posting Komentar