راهمنایی در مورد پیدا کردن کمترین فاصله بین نقاط در یک صفحه (تقسیم و حل)

[mahdi bg]

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

[ برای مشاهده لینک ، لطفا با نام کاربری خود وارد شوید یا ثبت نام کنید ]

ممنون

[mst_ab]

منظورت الگوریتمش هست یا زبان خاصی مد نظرته؟
کلیاتش اینه که باید دوتا حلقه تو در تو بنویسی که یک دو تایی مرتب رو دریافت کنه ( یعنی دو تا نقطه رو ) بعد برای هر بار اجرا شدن که به تعداد نقاط به توان 2بار اجرا خواهد شد، فاصله ی اون دو تا نقطه رو از هم پیدا کنه و در یک آرایه که قبلاً تعریف کردی بذاره. در نهایت کوچکترین (min) اون ها رو به عنوان کوتاه ترین فاصله برگردونه.
من این راه به ذهنم اومد و ممکنه راه ساده ی دیگه ای هم باشه.

[mst_ab]

البته یه چیزی رو که قبلاً در نظر نگرفته بودم اینه که برای نصفی از اونا تکراری اجرا میشه که برای اون هم باید یه فکری بکنی

[mahdi bg]

سلام


منظورت الگوریتمش هست یا زبان خاصی مد نظرته؟
کلیاتش اینه که باید دوتا حلقه تو در تو بنویسی که یک دو تایی مرتب رو دریافت کنه ( یعنی دو تا نقطه رو ) بعد برای هر بار اجرا شدن که به تعداد نقاط به توان 2بار اجرا خواهد شد، فاصله ی اون دو تا نقطه رو از هم پیدا کنه و در یک آرایه که قبلاً تعریف کردی بذاره. در نهایت کوچکترین (min) اون ها رو به عنوان کوتاه ترین فاصله برگردونه.
من این راه به ذهنم اومد و ممکنه راه ساده ی دیگه ای هم باشه.


این راحترین راه اما بازگشتی نیست



البته یه چیزی رو که قبلاً در نظر نگرفته بودم اینه که برای نصفی از اونا تکراری اجرا میشه که برای اون هم باید یه فکری بکنی

اگر بخواهی از این روش استفاده کنیم یک راه استفاده از یک
ماتریس بالا مثلثی یا پایین مثلثی است.