white-sheet

White Sheet

توجد ورقة بيضاء على طاولة. ثم توضع ورقتان سوداوان على الطاولة. كل الأوراق مستطيلات أضلاعها موازية لأضلاع الطاولة.

حدّد هل يمكن رؤية جزء من الورقة البيضاء من الأعلى. يمكن رؤية جزء إذا وُجدت نقطة تقع في الورقة البيضاء (مع حدودها) وخارج الورقتين السوداوين تمامًا.

القيود:

\(0 \le x_1 < x_2 \le 10^6\)، \(0 \le y_1 < y_2 \le 10^6\)، والأمر نفسه للورقتين السوداوين.

الإدخال:

السطر الأول: أربعة أعداد صحيحة \(x_1, y_1, x_2, y_2\) — الركن السفلي الأيسر والركن العلوي الأيمن للورقة البيضاء.
السطر الثاني: أربعة أعداد صحيحة \(x_3, y_3, x_4, y_4\) — الورقة السوداء الأولى.
السطر الثالث: أربعة أعداد صحيحة \(x_5, y_5, x_6, y_6\) — الورقة السوداء الثانية.

المخرجات:

YES إذا أمكن رؤية جزء من الورقة البيضاء، و NO في غير ذلك.

أمثلة:

الإدخال:

2 2 4 4
1 1 3 5
3 1 5 5

المخرجات:

NO

(الورقتان السوداوان تغطيان الورقة البيضاء كلها.)

الإدخال:

3 3 7 5
0 0 4 6
0 0 7 4

المخرجات:

YES

(مثلًا يمكن رؤية النقطة \((6.5, 4.5)\).)

الحل

يمكن رؤية الورقة البيضاء تمامًا عندما لا تغطي الورقتان السوداوان كل مساحتها.

إذا بقي جزء من الورقة البيضاء مساحته موجبة غير مغطّى، فيمكن رؤية نقاطه.
إذا كانت مساحة الجزء غير المغطّى صفرًا، فهو يتكوّن فقط من قطع ونقاط على حدود الورقتين السوداوين. هذه النقاط ليست خارج الورقتين السوداوين تمامًا، لذلك لا يمكن رؤيتها.

لذلك نحسب المساحة المغطّاة من الورقة البيضاء ونقارنها بمساحة الورقة البيضاء.

المساحة المغطّاة هي مساحة اتحاد \(W \cap B_1\) و \(W \cap B_2\)، حيث \(W\) الورقة البيضاء و \(B_1, B_2\) الورقتان السوداوان. عند جمع المساحتين يُحسب الجزء الذي تغطيه الورقتان السوداوان معًا مرتين، لذلك نطرحه مرة واحدة:

\[ \text{covered} = |W \cap B_1| + |W \cap B_2| - |W \cap B_1 \cap B_2| \]

نحسب كل تقاطع بالدوال من الدرس. \(W \cap B_1 \cap B_2\) هو تقاطع المستطيل \(W \cap B_1\) مع \(B_2\).

تصل المساحات إلى \(10^{12}\)، لذلك تستخدم الإحداثيات والمساحات النوع long long.

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

struct Point {
    long long x;
    long long y;
};

struct Rectangle {
    Point bottom_left;
    Point top_right;
};

long long area(Rectangle r) {
    long long width = r.top_right.x - r.bottom_left.x;
    long long 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;
}

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() {
    Rectangle white = read_rectangle();
    Rectangle black1 = read_rectangle();
    Rectangle black2 = read_rectangle();

    long long covered = 0;
    if (rectangles_intersect(white, black1)) {
        Rectangle part1 = rectangle_intersection(white, black1);
        covered += area(part1);

        // the part covered by both black sheets is counted twice
        if (rectangles_intersect(part1, black2)) {
            covered -= area(rectangle_intersection(part1, black2));
        }
    }
    if (rectangles_intersect(white, black2)) {
        covered += area(rectangle_intersection(white, black2));
    }

    if (covered < area(white)) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

نقاط يجب الانتباه لها

استدعِ rectangle_intersection فقط عندما تعيد rectangles_intersect القيمة true. وإلا فالنتيجة ليست مستطيلًا صحيحًا، وقد تكون “مساحتها” موجبة مع أن المستطيلين لا يتقاطعان.