Convex Hall 2D
مساله : تعدادی میخ روی یک تخته کوبیده شده ، یک کش دور آنها می اندازیم. کش روی کدام میخها می افتد؟ (کوچکترین چندضلعی محدبی که همه میخها را دربر میگیرد پیدا کنید)
الگریتم گراهام برای حل Convex Hall :
نقطه های P1,P2,...,Pn با مختصات (x1,y1),(x2,y2),...,(xn,yn) مفروض است.
1) نقطه q0 را با کمترین y پیدا میکنیم.
2) سایر نقاط را برحسب زاویه قطبی حول q0 مرتب می‌کنیم. و q1 تا qn-1 نامگذاری میکنم.
3)

Push(q0),Push(q1),Push(q2)

4)

for i=3 to n-1
while(rastgard(qi,stack[top],stack[top-1]))
pop()
wend
push(qi)
next

پیچیدگی زمانی این الگریتم nlogn است.

download (بدون فایل اجرایی.)
جوتی
حاشیه : این مساله 3d هم داره! خدا رحم کنه!

---