المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۲:عملی:سوال ۱۱

درخت بری

در یک جنگل عجیب تعدادی درخت وجود دارد. مختصات هر درخت عددهای صحیحی هستند.(دستگاه مختصات شبیه دستگاه مختصات معمولی است) درخت‌های این جنگل دارای این خاصیت عجیب هستند که به ازای هر دو درخت دلخواه اگر مختصات یکی $(x_i,y_i)$ و مختصات دیگری $(x_j,y_j)$ باشد،$x_i-x_j$ و $y_i – y_j$ هم علامت هستند.

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

ورودی

در خط اول فایل ورودی عدد $n$ (تعداد درختان) نوشته شده است. در $n$ سطر بعد در سطر $i+1$ ام به ترتیب $x_i$ و $y_i$ نوشته شده است. در سطر $n+2$ ام عدد $m$ (تعداد پیمانکارها )نوشته شده است. در $m$ سطر بعد به ترتیب اطلاعات پیمانکارها نوشته شده است. در هر سطر به ترتیب $X_1$ و $Y_1$ و $X_2$ و $Y_2$ و $c$ نوشته شده است که $(X_1,Y_1)$ مختصات گوشه‌ی پایین و چپ و $(X_2,Y_2)$ مختصات گوشه‌ی بالا و راست محدوده‌ی مربوط به این پیمانکار است. $c$ پولی است که این پیمانکار برای بریدن درختان این قسمت می‌گیرد.

خروجی

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

محدودیت‌ها

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

ابزار صفحه