Cho ña giaùc goàm N ñænh (D[1..n]) vaø ñieåm M. Kieåm tra xem M
coù thuoäc ña giaùc ñaõ cho hay khoâng
Döõ lieäu
vaøo: Doøng ñaàu tieân goàm soá N – soá ñænh cuûa ña giaùc, N doøng
tieáp theo moãi doøng goàm 2 soá x vaø y laø toïa ñoä moãi ñænh, doøng cuoái
cuøng laø toïa ñoä ñieåm M (x0,y0).
Döõ lieäu
ra: ghi soá 1 hoaëc soá 0 töông öùng laø thuoäc hoaëc khoâng thuoäc
ña giaùc ñaõ cho.
Höôùng daãn:
-Hieån nhieân laø neáu M thuoäc baát kì caïnh naøo cuûa ña giaùc
thì M thuoäc ña giaùc ñoù.
-Ngöôïc laïi, ta keû ñoaïn thaúng MN song song vôùi truïc hoaønh sao
cho hoaønh ñoä cuûa N lôùn hôn hoaønh ñoä lôùn nhaát trong N ñænh, töùc laø
max(x1..N). Ta ñi tìm giao ñieåm caùc caïnh cuûa ña giaùc vôùi ñoaïn
thaúng MN, neáu soá giao ñieåm laø chaün thì M naèm ngoaøi ña giaùc coøn ngöôïc
laïi M thuoäc mieàn ña giaùc.
-Thöû xeùt moät caïnh baát kì cuûa ña giaùc, laø caïnh (D[i],D[i+1]
), ta taêng soá löôïng giao ñieåm leân trong caùc tröôøng hôïp sau:
1. Ñænh D[i] khoâng
thuoäc MN, ñænh D[i+1] thì thuoäc MN, hai ñænh D[i] vaø D[i+2] naèm khaùc phía
so vôùi MN.
2. ñænh D[i-1] vaø D[i+2] naèm ngoaøi MN, hai
ñænh D[i] vaø D[i+1] thuoäc MN, hai ñænh D[i-1] vaø D[i+2] khaùc phía so vôùi
MN.
3. ñænh D[i] vaø D[i+1] khoâng thuoäc MN vaø
caïnh (D[i],D[i+1]) caét MN.
