المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۹:سوال ۶

Points

تعدادی نقطه به شما داده شده است، شما می‌توانید تعدادی از این نقاط را به وسیله‌ی پاره‌خط‌هایی به هم وصل کنید به‌طوری‌که هیچ دو پاره‌خطی با هم برخورد نداشته باشند (مگر در نقاط انتهایی) و هر راس به دو یا صفر راس دیگر به‌وسیله‌ی این پاره‌خط‌ها وصل باشد. با انجام این کار تعدادی چند ضلعی به وجود خواهد آمد، شما باید طوری این کار را انجام دهید که جمع مساحت‌های این چند ضلعی‌ها بیشینه شود.

برنامه‌ای بنویسید که

  • مختصات تعدادی نقطه را از ورودی بخواند. مختصات نقاط صحیح است و نقطه‌ی تکراری نیز نداریم.
  • بیش‌ترین مجموع مساحت ممکن برای چندضلعی‌های غیر متقاطع‌ای که با این نقاط می‌توان ساخت را بدست آورده و این مقدار را در خروجی چاپ نمایید.

ورودی

  • در سطر اول ورودی ‎$n$‎ تعداد نقاط می آید.
  • در هر یک از ‎$n$‎ سطر بعدی مختصات یکی از این نقاط آمده است.
  • تعداد نقاط حداقل برابر ‎۳‎ و حداکثر برابر ‎۲۰۰۰‎ است.
  • هیچ سه نقطه‌ای روی یک خط قرار ندارند.
  • مختصات نقاط بین ‎$(-10000,-10000)$‎ و ‎$(10000,10000)$‎ قرار دارند.

خروجی

در تنها سطر خروجی جواب مسئله را تا دو رقم اعشار چاپ کنید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
8‎
-‎11‎ -‎7‎
-11 7‎
11‎ -‎7‎
11 7‎
-3‎ -‎5‎
-‎3 5‎
3‎ -‎5‎
3 5
368.00


ابزار صفحه