Эх өгүүлбэр
Энэ бодлого нь өгөгдсөн цэг өгөгдсөн гурвалжин дотор орших уу гэдгийг шалгах бодлоготой төсгэй юм. Өгөгдсөн цэгийг оройн цэгүүдтэй болбоход дөрвөн пирамид үүснэ. Эдгээр дөрвөн пирамидын эзэлхүүнүүдын нийлбэр өгөгдсөн пирамидын эзэлхүүнтэй тэнцүү бол дотор нь үгүй бол гадана нь оршно. Пирамидын эзэлхүүнийг
|x1-x0, y1-y0, z1-z0|
|x2-x0, y2-y0, z2-z0|
|x3-x0, y3-y0, z3-z0|
тодорхойлогчийг бодох замаар олж болно. Пирамидын эзэлхүүнийг O(1) хугацаанд бодно. Тиймээс O(n) хугацаанд бодно.
No comments:
Post a Comment