Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

Floyd-Warshall

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

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

ورودی

  • در سطر اول دو عدد n و m آمده ست.
  • در n خط بعد مختصات نقاط قرمز و در m خط بعد آن مختصات نقاط آبی آمده است.
  • 1n,m500
  • |x|,|y|109

خروجی

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

محدودیت‌ها

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

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

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

پاسخ

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


ابزار صفحه