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

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

ملحوظة

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

تمثيل المستطيلات

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

ملحوظة

في هذا القسم سنمثل المستطيل باستخدام إحداثيات الزاوية العليا اليمنى و السفلى اليسرى، حيث \(tr_x\) و \(tr_y\) هي إحداثيات النقطة العليا اليمنى، و \(bl_x\) و \(bl_y\) هي إحداثيات النقطة السفلى اليسرى.

المعادلات الشائعة

الطول والعرض

\(length\) هو الطول للمستطيل بينما \(width\) هو العرض.

\(width = tr_x - bl_x\)

\(length = tr_y - bl_y\)

المساحة

المساحة (\(area\)) للمستطيل هو حاصل ضرب الطول (\(length\)) في العرض (\(width\)).

\(area = length \cdot width\)

int area(int bl_x, int bl_y, int tr_x, int tr_y) {
  int length = tr_y - bl_y;
  int width = tr_x - bl_x;
  return length * width;
}

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

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

لبعد \(Y\):

\(a_{tr_y} \le b_{bl_y}\) أو \(b_{tr_y} \le a_{bl_y}\)

لبعد \(X\):

\(a_{tr_x} \le b_{bl_x}\) أو \(b_{tr_x} \le a_{bl_x}\)

إذا تحقق أي من ذلك، المستطيلان لا يتقاطعان، وإلا فإنهما يتقاطعان.

bool are_intersected(int a_tr_x , int a_tr_y, int a_bl_x, int a_bl_y, int b_tr_x , int b_tr_y, int b_bl_x, int b_bl_y) {
  if(a_tr_y <= b_bl_y || b_tr_y <= a_bl_y || a_tr_x <= b_bl_x || b_tr_x <= a_bl_x) {
    return false;
  }
  else {
    return true;
  }
}

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

إذا كان مستطيلان \(a\) و \(b\) يتقاطعان، فإن المستطيل \(c\) الذي يمثل التقاطع يكون:

\(c_{tr_x} = min(a_{tr_x}, b_{tr_x})\)
\(c_{tr_y} = min(a_{tr_y}, b_{tr_y})\)
\(c_{bl_x} = max(a_{bl_x}, b_{bl_x})\)
\(c_{bl_y} = max(a_{bl_y}, b_{bl_y})\)

المعادلات أحادية البعد

تنطبق هذه الهندسة أيضًا في فضاء أحادي البعد، حيث نعمل مع المحالات بدلاً من المستطيلات. يمثل المجال برقمين، \(l\) و \(r\)، واللذان يمثلان بداية ونهاية المجال.

المعادلات

الطول

\(length\) هو المساحة المغطاة بواسطة المجال.

\(length = r - l\)

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

لمجالين \(a\) و \(b\) في بعد واحد، يمكننا التحقق مما إذا لم يتقاطعا. إذا كانت أحد المجالين يقع بالكامل على يسار أو يمين الآخر، فهو لا يتداخل. وإلا، فإن المجالين يتقاطعان:

\(a_{r} \le b_{l}\) أو \(b_{r} \le a_{l}\)

bool are_intersected(int a_l , int a_r, int b_l , int b_r) {
  if(b_l <= a_r || a_l <= b_r) {
    return false;
  }
  else {
    return true;
  }
}

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

إذا كان المجالين \(a\) و \(b\) يتقاطعان، فإن المجال \(c\) الذي يمثل التقاطع يكون:

\(c_{l} = max(a_{l}, b_{r})\)
\(c_{r} = min(a_{l}, b_{tr_y})\)

مثال على مهمة

Fence Painting

USACO

لدينا مجالين \(a\) و \(b\)ويُطلب طباعة المساحة الإجمالية المغطاة من قبل هذين المجالين.

Solution

إذا لم يتقاطع المجالين، فإن المساحة المغطاة هي مجموع الطولين. وإلا، فإن الحل يكون مجموع الطولين مطروحًا منه مساحة التقاطع.

#include <iostream>

using namespace std;

int main() {
  // USACO هذين السطرين فقد لأخذ المدخلات وطباعة المخرجات في موقع 
  freopen("paint.in", "r", stdin);
  freopen("paint.out", "w", stdout);

  int a_l , a_r, b_l , b_r;
  
  cin >> a_l >> a_r >> b_l >> b_r;

  // b و a يمثل التقاطع بين c
  int c_l = max(a_l, b_l), c_r = min(a_r, b_r);

  int total = (a_r - a_l) + (b_r - b_l);
  int intersection = (c_r - c_l);
  
  // يتقاطعان b و a الآن يجب أن نتحقق ما إذا 
  if(b_l > a_r || a_l > b_r){
    cout << total << "\n";
  }
  else{
    cout << total - intersection << "\n";
  }
}