هندسة المستطيلاتRectangular Geometry

تختص هندسة المستطيلات بالمستطيلات التي تكون أضلاعها موازية لمحوري الإحداثيات. يشرح هذا القسم العمليات الأساسية المستخدمة مع هذه المستطيلات.

ملاحظة

نفترض أن الاتجاه الموجب للمحور \(X\) يشير إلى اليمين، وأن الاتجاه الموجب للمحور \(Y\) يشير إلى الأعلى.

تمثيل النقاط والمستطيلات

تحتوي النقطة على إحداثيين: إحداثي \(x\) وإحداثي \(y\). يمكننا جمعهما في بنية واحدة:

struct Point {
    int x;
    int y;
};

يمكن تمثيل المستطيل الموازي للمحورين بنقطتي الزاوية السفلية اليسرى والزاوية العلوية اليمنى. نجمع هاتين النقطتين في بنية أخرى:

struct Rectangle {
    Point bottom_left;
    Point top_right;
};

نفترض في هذا القسم أن إحداثيات كل مستطيل مرتبة كما يلي:

bottom_left.x <= top_right.x
bottom_left.y <= top_right.y

العمليات الشائعة على المستطيلات

العرض والارتفاع والمساحة

العرض هو المسافة الأفقية بين ضلعي المستطيل:

width = r.top_right.x - r.bottom_left.x

الارتفاع هو المسافة العمودية بين ضلعي المستطيل:

height = r.top_right.y - r.bottom_left.y

المساحة هي حاصل ضرب العرض في الارتفاع:

area = width * height

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;
}

التحقق من التقاطع

يتقاطع مستطيلان بمساحة موجبة فقط إذا تداخل مجالاهما على المحور \(X\) وعلى المحور \(Y\). غالبًا ما يكون التحقق من الحالة العكسية أسهل.

يكون المستطيلان منفصلين أفقيًا إذا انتهى أحدهما عند بداية الآخر أو قبلها. وينطبق الشرط نفسه عموديًا باستخدام إحداثيات المحور \(Y\). إذا تحقق أي من شرطي الانفصال، فلا يتقاطع المستطيلان.

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;
}

ملاحظة

إذا تلامس المستطيلان عند ضلع أو زاوية فقط، فإن مساحة الجزء المشترك تساوي صفرًا؛ لذلك لا نعدهما متقاطعين.

إيجاد التقاطع

إذا تقاطع المستطيلان a وb، فإن تقاطعهما يكون مستطيلًا آخر. نأخذ لكل إحداثي في النقطة السفلية اليسرى القيمة الكبرى، ولكل إحداثي في النقطة العلوية اليمنى القيمة الصغرى.

#include <algorithm>
using namespace std;

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_intersection إلا بعد أن تؤكد الدالة rectangles_intersect وجود تقاطع.

الهندسة أحادية البعد

تنطبق الأفكار نفسها في بعد واحد، حيث نتعامل مع الفترات بدلًا من المستطيلات. تحتوي الفترة على طرف أيسر وطرف أيمن:

struct Interval {
    int left;
    int right;
};

نفترض أن طرفي كل فترة مرتبان، أي إن left <= right.

الطول

يُحسب طول الفترة كما يلي:

length = segment.right - segment.left

int length(Interval segment) {
    return segment.right - segment.left;
}

التحقق من التقاطع

تتقاطع فترتان بطول موجب ما لم تنتهِ إحداهما عند بداية الأخرى أو قبلها:

bool intervals_intersect(Interval a, Interval b) {
    return a.right > b.left && b.right > a.left;
}

كما في المستطيلات، إذا اشتركت الفترتان في طرف واحد فقط، فإن طول التقاطع يساوي صفرًا ولا نعدهما متقاطعتين.

إيجاد التقاطع

إذا تقاطعت الفترتان a وb، فإن فترة التقاطع تبدأ عند الطرف الأيسر الأكبر وتنتهي عند الطرف الأيمن الأصغر:

#include <algorithm>
using namespace std;

Interval interval_intersection(Interval a, Interval b) {
    Interval c;
    c.left = max(a.left, b.left);
    c.right = min(a.right, b.right);
    return c;
}

مثال على مسألة

طلاء السياج

USACO

لدينا فترتان، والمطلوب طباعة الطول الإجمالي الذي تغطيانه.

الحل

نجمع طولي الفترتين، ثم نطرح طول الجزء الذي تغطيانه معًا. إذا لم تتداخل الفترتان، يكون طول الجزء المشترك صفرًا.

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

struct Interval {
    int left;
    int right;
};

int length(Interval segment) {
    return segment.right - segment.left;
}

int overlap_length(Interval a, Interval b) {
    int left = max(a.left, b.left);
    int right = min(a.right, b.right);
    return max(0, right - left);
}

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

    Interval a, b;
    cin >> a.left >> a.right >> b.left >> b.right;

    int total = length(a) + length(b) - overlap_length(a, b);
    cout << total << "\n";
}