المپدیا

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

ابزار کاربر

ابزار سایت


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

مثلث‌ها

تعدادی مثلث قائم‌الزاویه‌ی متساوی‌الساقین سیاه که اضلاع زاویه‌ی قائم آن‌ها موازی محورهای مختصات بوده و مختّصات تمام رئوس آن‌ها صحیح است، در صفحه‌ی دو بعدی سفید به ما داده شده‌است.

می‌دانیم بعضی از این مثلث‌ها با هم، هم‌پوشانی‎ دارند. می‌خواهیم مساحت کل ناحیه‌ی سیاه اشغال شده توسّط این مثلث‌ها را در صفحه بیابیم.

برنامه‌ای بنویسید که

  • تعداد مثلث‌ها و مختصات ‎۳‎ رأس هر کدام از آن‌ها را از ‎ورودی‎ بخواند.
  • مساحت کل ناحیه‌ی سیاه‌شده توسط این مثلث‌ها را محاسبه کند.
  • نهایتاًاین مساحت را در خروجی بنویسد.

‎ورودی

  • در سطر اوّل ورودی تعداد مثلث‌ها ‎($n$)‎ آمده است.
  • در هر یک از ‎$n$‎ سطر بعدی، ‎۶‎ عدد آمده است که مختصّات ‎۳‎ رأسِ ‎$b$‎، ‎$a$‎ و ‎$c$ (به‌ترتیب دلخواه) از یک مثلث به‌صورت ‎$x_a‎~ ‎y_a‎~ ‎x_b‎~ ‎y_b‎~ ‎x_c‎~ ‎y_c$‎ نوشته شده است.
  • $1 \le n \le 222$‎.
  • تمام مختصه‌های تمام رئوس تمام مثلث‌ها دربازه‌ی ‎$[-222‎, ‎222]$‎ قرار دارند.

‎‎خروجی

در تنهای سطر خروجی مساحت ناحیه‌ی اشغال شده توسّط این مثلث‌ها را ‎ تا دو رقم اعشار بنویسید.

محدودیت‌ها

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

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

ورودي نمونه خروجي نمونه
4
‎5 5 5 6 4 6
‎1 2 5 6 5 2
‎1 4 1 1 4 1
‎0 0 0 1 1 0‎
‎12.25

ابزار صفحه