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

المپدیا

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

ابزار کاربر

ابزار سایت


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

Convex Hull

برنامه‌ای بنویسید که تعدادی نقطه را از ورودی استاندارد دریافت کند و پوش محدب این نقاط را حساب کند.

ورودی

  • در سطر اول ورودی n، تعداد نقاط آمده است.
  • در هر یک از n سطر بعدی دو عدد صحیح x و y آمده است که مختصات یک نقطه را تعیین می‌کند.
  • تمام نقطه‌های ورودی متمایزند و هیچ سه نقطه‌ای هم خط نیستند.
  • 3n105
  • 109x,y109

خروجی

در سطر اول خروجی شما باید تعداد رئوس پوش محدب و در سطر بعد سپس‌ راس‌ها را به‌ترتیب صعودی بنویسید (اول بر حسب x و سپس بر حسب y).

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3
0 0
0 1
1 0
3
0 0
0 1
1 0

پاسخ

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


ابزار صفحه