معرفی
در این مقاله، حداکثر تعداد نقاطی را که روی یک خط مستقیم قرار دارند، پیدا می کنیم.
بیان مسأله
با توجه به n نقطه در یک صفحه دو بعدی، حداکثر تعداد نقاطی را که روی همان خط مستقیم قرار دارند، پیدا کنید.
مثال 1
ورودی: [1،1]، [2،2]، [3،3]
خروجی: 3
توضیح
![](http://pezhvak24.ir/dl/codenevis/firstcode/article/max-points-on-a-line/Images/Example1.png)
مثال 2
ورودی: [1،1]، [3،2]، [5،3]، [4،1]، [2،3]، [1،4]
خروجی: 4
توضیح
![](http://pezhvak24.ir/dl/codenevis/firstcode/article/max-points-on-a-line/Images/Example2.png)
راه حل
بیایید مسئله را ساده کنیم و حداکثر تعداد نقاط روی خطی را که از نقطه i می گذرد جستجو کنیم. بلافاصله می توان متوجه شد که جالب است فقط نقاط بعدی i + 1 .. N - 1 را در نظر بگیریم زیرا حداکثر تعداد نقاط حاوی، برای مثال، نقطه i - 2 قبلاً در طول جستجوی حداکثر تعداد نقاط در پیدا شده است. خطی که از نقطه i – 2 می گذرد. ایده بسیار ساده است: خطوطی را که از نقطه i و هر یک از نقاط بعدی عبور می کنند رسم کنید. ذخیره این خطوط یک جدول هش با شمارنده 2 = دو نقطه در این خط است.