Processing math: 86%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۶:عملی:سوال ۲

گراف فضایی

یک مسیر ‎n‎ راسی در یک گراف دنباله‌ای به طول ‎n‎ از رئوس است. یک مسیر فضایی ‎n‎ راسی دنباله‌ای از نقاط است که در یک صفحه آمده اند و به صورت یک مسیر به ترتیب به هم وصل هستند. فاصله دو راس مجاور ‎i‎ و ‎i+1‎ برابر طول یال آن‌ها می‌باشد ( طول یال در فضا برابر مقدار فاصله دو نقطه در صفحه اقلیدسی می‌باشد). فاصله فضایی دو راس ‎i‎ و ‎j‎ مجموع طول یال‌هایی می‌باشد که راس ‎i‎ را به راس ‎j‎ می‌رساند ( مسیر متصل کننده این دو راس ‎(‎.

هدف پیدا کردن بیش‌ترین مقدار نسبت فاصله فضایی دو راس ‎i‎ و ‎j‎ به فاصله اقلیدسی آن‌ها می‌باشد.

ورودی

  • در سطر اول ورودی 2n1000‎ ‎ تعداد نقاط آمده است.
  • در ‎n‎ سطر بعدی در هر سطر دو عدد صحیح 0 \leq x_i‎ , ‎y_i \leq 10000‎ ‎آمده است که مختصات نقطه ‎i‎ام در صفحه می‌باشد.

خروجی‎

در تنها سطر فایل خروجی قسمت صحیح مقدار بیشینه نسبت فاصله فضایی و فاصله اقلیدسی را بنویسید.

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
‎4
‎0 1
2 3‎
‎3 3
‎1 1‎
6

ابزار صفحه