مختصات دو نقطه با کمترین فاصله

[الهه-ت]

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

[Hsn.Zare]

با سلام به شما دوست عزیز
اگر بخوای این مساله رو به روش تقسیم حل , حل کنی اندازه مساله که هر دفعه باید شکسته بشه رو می تونی عرض صفحه ای در نظر بگیری که نقاطت در اون قرار دارند .
فرض کن نقاط توی یه صفحه مختصات دکارتی اند . شما این صفحه رو از سمت X ها می شکنی . دو تا صفحه جدید به دست میاد . اون دوتا صفحه جدید اندازه جدید مساله می شند و جدا باید به همین روش حل شن . مشکلی که هست اینه که شاید نقطه ای از زیر صفحه سمت چپ با زیر با نقطه ای از زیر صفحه سمت راست کمترین فاصله رو داشته باشه . پس باید یه ناحیه هم اون وسط بگیری . که تنها نکته طول این ناحیه است . بهترین راهی که به ذهن من می رسه اینه که :
اول در هر دو ناحیه کم ترین فاصله رو پیدا کن .
بعد به اندازه کوچکترین اونا ، از زیر صفحه سمت راست برو سمت چپ و از زیر صفحه سمت چپ برو سمت راست . یعنی یه صفحه جدید بین اون دو صفحه با طول دو برابر کمترین فاصله بین اون دو زیر فاصله .

[molla652003]

تو کتاب CLRS ( همون introduction to algorithms ) تو قسمت geometry کامل توضیح داده.

[ali_habibi1384]

حالا چرا تقسیم و حل؟ از راه های دیگه ای نمیشه استفاده کرد؟

[pesar irooni]

با عرض سلام خدمت شما دوست عزیز
من هم با نظر این دوستمون موافقم. باید با روش "تقسی و حل" این مساله رو حل کرد. ولی برای حل مشکل نقاط دو طرف خط بهتر در زیر صفحه ها بهتره به جای تقسیم به دو زیر صفحه، صفحمون رو به سه زیر صفحه تقسیم کنیم که دو زیر صفحه بالا و پایین خطی که از وسط صفحه رد میشه و یک زیر صفحه میانی که فاصله اش از دو طرف خط میانی یک اندازست. بنابر این مشکل نقاطی که در دو زیر صفحه بالا و پایین و نزدیک خط تقسیم هستند حل میشه.. فقط اشکالش اینه که بعضی از نقاط ممکن دو بار بررسی بشند که البته فکر نمی کنم اشکالی داشته باشه. بجاش جواب درست رو میگیری اونم با روش تقسیم و حل