- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
برای برگزاری اختتامیه کدکاپ، یک فضای باز در کویری صاف و بی‌آب و علف در نظر گرفته‌ایم. از قبل روی زمین $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
ارسال پاسخ برای این سؤال