المپدیا

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

ابزار کاربر

ابزار سایت


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

Sweepline

تعدادی مستطیل در صفحه داده شده‌است. مساحت اجتماع آن‌ها را به‌دست آورید.

ورودی

  • در خط اول ورودی $n$ تعداد مستطیل‌ها آمده است.
  • سپس در هر خط مختصات دو رأس روبروی یک مستطیل آمده است. $(x_1, y_1)$ و $(x_2, y_2)$
  • $1 \leq n \leq 10^5$
  • $-10^9 \leq x_1, y_1, x_2, y_2 \leq 10^9$

خروجی

در تنها سطر خروجی مساحت اجتماع مستطیل‌ها را چاپ کنید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
2
20 20 10 10
30 25 15 15
225

پاسخ

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


ابزار صفحه