این سوال اسمش هست "پوش محدب" یا "convex hull". این شبه کد الگوریتم هست.

توضیح الگوریتم : http://activities.tjhsst.edu/sct/lectures/0910/convex_hull.pdf و http://paste.ubuntu.com/7586898/.

نکته : $zcrossprod(a,b)$ برابر ضرب خارجی دو بردار $a$ و $b$ است و $zcrossprod(a,b) = a_x * b_y - a_y * b_x = |a| * |b| * sin(\alpha)$ که $\alpha$ زاویه بین دو بردار $a$ و $b$ است. و $q-p$ که $p$ و $q$ نقطه اند برداری است که $p$ را به $q$ متصل میکند و برابر $(q_x-p_x, q_y-p_y)$ است.

در ضمن برای محاسبه مساحت یک $n$ ضلعی که مختصات نقاط آن برابر $(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$ است لازم نیست آن را مثلث بندی کنیم ! بلکه این مقدار (مساحت) برابر است با :$x_1y_2 + x_2y_3 + ... + x_ny_1 - y_1x_2 - y_2x_3 - ... - y_nx_1$

منابع :http://ace.delos.com/usacogate بخش 3.4 ، TEXT Computational Geometry و بخش 5.1 ، TEXT Convex Hulls .

با سلام الگوریتم میتواند اینگونه باشد :

ابتدا از نقطه ای که بیشترین فاصله از مبدا را دارد شروع می کنیم بعد به دومین نقطه نزدیک یک خط میکشیم بعد می بینیم که ایا نزدیک ترین نقطه توی این خط است یا بیرون (یعنی توی پند ضلعی می افتد یا بیرون که تایین این با توجه به این که سمت راست داریم حرکت می کنیم یا چپ امکان پذیر است)

اگر تو بود حال دومی را با سومی ، اگر آن هم دومی تو بود دو باره سومی با چهارمی .. و همین گونه ادامه می دهیم تا به نقطه ای برسیم که اگر از نقطه ی اول به نقطه ی بعدی آن خط بکشیم آن نقطه بیرون بیفتد بعد از نقطه ی اول به آن خط می کشیم.حالا مبدا رو نقطه ی دوم میگذاریم و همین طور ادامه می دهیم تا به نقطه ی شروع برسیم و از آن جایی که نقطه ی شروع را نقطه ای به دور ترین فاطله از مبدا قرار دادیم حتما دوباره به آن میرسیم.

خب حالا بزرگترین چند ضلعی رو داریم و دلیلش که هم واضح است زیرا همه ی نقاط یا توی شکل اند یا روی آن.

برای محاسبه مساحت هم می توانیم آن را به چند مثلث افراز کنیم و مساحت آن مثلث ها را با رابطه ی ضرب دو ضلع و زاویه بین آن ها تقسیم بر 2 حساب میکنیم .

خیلی طولانیییی شد.

امیدوارم به کار بیاد