- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
برای برگزاری اختتامیه کدکاپ، یک فضای باز در کویری صاف و بیآب و علف در نظر گرفتهایم. از قبل روی زمین \(n\) ستون قرار دارد. اگر این محوطه را به صورت صفحهی مختصات دوبعدی در نظر بگیریم. ستونها مانند نقطههایی مثل \((x_1, y_1), (x_2,. y_2), \dots, (x_n, y_n)\) در صفحه هستند.
مدیر مسابقات میخواهد یک طناب دور این ستونها بکشد و محوطه اختتامیه را مشخص کند. او میخواهد طوری این طناب را بکشد، که همهی ستونها داخل محوطه قرار بگیرند و طول طنابی که استفاده میشود، کمینه باشد.
به طرز عجیبی یکی از این \(n\) ستون از محوطه حذف شده ولی نمیدانیم کدام ستون است، برای همین برای هر \(i = 1, 2, \dots, n\,\) بررسی کنید اگر ستون \((x_i, y_i)\) در زمین نباشد، محیط طنابی که باید بکشیم چقدر است.
همچنین میدانیم هیچ دو ستونی روی هم قرار نگرفته و مساحت ناحیهی مشخص شده برای محوطه، همواره (برای هر ستونی که نباشد)، مثبت بدست میآید.
ورودی
در سطر اول ورودی، عدد صحیح و مثبت \(n\) آمده است.
\[4 \leq n \leq 100 \, 000\]
در \(n\) سطر بعدی، در هر سطر دو عدد \(x_i\) و \(y_i\) آمده که مختصات ستون \(i\)ام را نشان میدهد.
\[-10^9 \leq x, y \leq 10^9\]
تضمین میشود هیچ دو ستونی روی هم نباشند و مساحت ناحیهی مشخص شده برای محوطه، همواره مثبت بدست میآید.
خروجی
در \(n\) سطر پاسخ مسئلهها را چاپ کنید. در سطر \(i\)ام حداقل طول طناب مورد نیاز در صورت نبودن ستون \(i\)ام را چاپ کنید.
پاسخ شما زمانی پذیرفته میشود که اختلاف آن با جواب درست حداکثر \(10^{-3}\) باشد.
مثالها
ورودی نمونه ۱
5
2 0
0 2
0 0
2 1
4 1
خروجی نمونه ۱
10.246211251
8.472135955
9.187600728
10.359173603
7.236067977
ورودی نمونه ۲
4
-3 0
0 -1
3 0
0 3
خروجی نمونه ۲
11.404918347
14.485281374
11.404918347
12.324555320
ارسال پاسخ برای این سؤال