المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۸:الگوریتم ها:سوال ۱۱

سوال ۱۱

رئوس یک چندضلعی محدب $n$ ضلعی داده شده است. مختصات رئوس این چندضلعی به ترتیب به صورت $(x_1,y_1)$، $(x_2,y_2)$، …، $(x_n,y_n)$ می‌باشند. الگوریتمی با کارایی $O(n)$ ارائه دهید که زوج راسی از چندضلعی که بیش‌ترین فاصله را دارند، بیابد. توجه دارید که باید صورت دقیق الگوریتم را بدون ابهام ارائه کنید و درستی الگوریتم را ثابت کنید و کارایی آن را دقیقا محاسبه نمایید.


ابزار صفحه