المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های تمرینی دوره ی تابستان:سوال ۴۶

Floyd-Warshall

$n$ نقطه قرمز و $m$ نقطه آبی روی صفحه داده شده است. یک چندضلعی ساده بیابید که:

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

ورودی

  • در سطر اول دو عدد $n$ و $m$ آمده ست.
  • در $n$ خط بعد مختصات نقاط قرمز و در $m$ خط بعد آن مختصات نقاط آبی آمده است.
  • $1 \leq n, m \leq 500$
  • $|x|, |y| \leq 10^9$

خروجی

در صورت وجود جواب؛ در خروجی محیط چندضلعی را با ۳ رقم اعشار چاپ کنید؛ در غیر این صورت عبارت «NO» را چاپ کنید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
4 1
0 0
0 2
2 0
2 2
1 1
8.000

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه