blocked-billboard

Blocked Billboard

تنظر بيسي إلى لوحتين إعلانيتين مستطيلتين. توقفت شاحنة مستطيلة أمامهما وقد تغطي جزءًا منهما. أوجد المساحة الكلية المرئية من اللوحتين.

الإدخال (الملف billboard.in):

السطر الأول: أربعة أعداد صحيحة \(x_1, y_1, x_2, y_2\) — الركن السفلي الأيسر \((x_1, y_1)\) والركن العلوي الأيمن \((x_2, y_2)\) للوحة الأولى.
السطر الثاني: اللوحة الثانية بالصيغة نفسها.
السطر الثالث: الشاحنة بالصيغة نفسها.

كل الإحداثيات بين \(-1000\) و \(1000\). اللوحتان لا تتداخلان (مساحتهما المشتركة صفر).

المخرجات (الملف billboard.out):

عدد صحيح واحد — المساحة المرئية الكلية.

مثال:

الإدخال:

1 2 3 5
6 0 10 4
2 1 8 3

المخرجات:

(يبقى مرئيًا \(5\) وحدات من اللوحة الأولى و \(12\) وحدة من اللوحة الثانية.)

الحل

اللوحتان لا تتداخلان، لذلك يمكننا معالجة كل منهما وحدها ثم جمع النتيجتين.

الجزء المرئي من اللوحة هو مساحتها ناقص المساحة التي تغطيها الشاحنة. الجزء المغطّى هو تقاطع اللوحة مع الشاحنة، ونحسبه بالدوال من الدرس:

إذا أعادت rectangles_intersect القيمة false، فاللوحة كلها مرئية؛
وإلا نطرح مساحة rectangle_intersection.

تقرأ مسائل USACO الإدخال من ملف وتكتب المخرجات في ملف. الدالة freopen تربط cin و cout بهذين الملفين.

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;

struct Point {
    int x;
    int y;
};

struct Rectangle {
    Point bottom_left;
    Point top_right;
};

int area(Rectangle r) {
    int width = r.top_right.x - r.bottom_left.x;
    int height = r.top_right.y - r.bottom_left.y;
    return width * height;
}

bool rectangles_intersect(Rectangle a, Rectangle b) {
    bool separated_x = a.top_right.x <= b.bottom_left.x ||
        b.top_right.x <= a.bottom_left.x;
    bool separated_y = a.top_right.y <= b.bottom_left.y ||
        b.top_right.y <= a.bottom_left.y;
    return !separated_x && !separated_y;
}

Rectangle rectangle_intersection(Rectangle a, Rectangle b) {
    Rectangle c;
    c.bottom_left.x = max(a.bottom_left.x, b.bottom_left.x);
    c.bottom_left.y = max(a.bottom_left.y, b.bottom_left.y);
    c.top_right.x = min(a.top_right.x, b.top_right.x);
    c.top_right.y = min(a.top_right.y, b.top_right.y);
    return c;
}

// area of the part of billboard b that the truck does not cover
int visible_area(Rectangle b, Rectangle truck) {
    if (!rectangles_intersect(b, truck)) {
        return area(b);
    }
    return area(b) - area(rectangle_intersection(b, truck));
}

Rectangle read_rectangle() {
    Rectangle r;
    cin >> r.bottom_left.x >> r.bottom_left.y >> r.top_right.x >> r.top_right.y;
    return r;
}

int main() {
    freopen("billboard.in", "r", stdin);
    freopen("billboard.out", "w", stdout);

    Rectangle b1 = read_rectangle();
    Rectangle b2 = read_rectangle();
    Rectangle truck = read_rectangle();

    cout << visible_area(b1, truck) + visible_area(b2, truck) << "\n";
}