Skip to content

📐 Правоъгълници и Координатна Геометрия

Задачите с правоъгълници, чиито страни са успоредни на координатните оси (Axis-Aligned Bounding Box - AABB), са изключително често срещани. Те са основата за по-сложни алгоритми като Sweep-Line и Segment Trees.

1. Представяне

Най-удобният начин за съхранение е чрез координатите на долния ляв \((x_1, y_1)\) и горния десен \((x_2, y_2)\) връх. Важно: Уверете се, че \(x_1 \le x_2\) и \(y_1 \le y_2\).

struct Rect {
    long long x1, y1, x2, y2; // Използвайте long long за да избегнете overflow при площ

    long long width() const { return max(0LL, x2 - x1); }
    long long height() const { return max(0LL, y2 - y1); }
    long long area() const { return width() * height(); }
};

2. Основни операции

2.1. Сечение (Intersection)

Сечението на два правоъгълника \(A\) и \(B\) също е правоъгълник (или празно множество). Координатите му се получават чрез вземане на "вътрешните" граници: max от левите/долните и min от десните/горните.

Rect intersect(const Rect& a, const Rect& b) {
    Rect res;
    res.x1 = max(a.x1, b.x1);
    res.y1 = max(a.y1, b.y1);
    res.x2 = min(a.x2, b.x2);
    res.y2 = min(a.y2, b.y2);

    // Ако е невалиден (с отрицателни страни), връщаме нулев
    if (res.x1 >= res.x2 || res.y1 >= res.y2) 
        return {0, 0, 0, 0};

    return res;
}

2.2. Обединение (Union Area)

За разлика от сечението, обединението на правоъгълници не е непременно правоъгълник. Обикновено се търси площта на обединението.

За 2 правоъгълника (Принцип на включване и изключване): \(S(A \cup B) = S(A) + S(B) - S(A \cap B)\)

За 3 правоъгълника: \(S(A \cup B \cup C) = S(A) + S(B) + S(C) - S(A \cap B) - S(A \cap C) - S(B \cap C) + S(A \cap B \cap C)\)

За \(N\) правоъгълника се използва методът на Замитащата права (Sweep Line), който е разгледан в Тема 27.

2.3. Точка в правоъгълник

bool contains(const Rect& r, long long x, long long y) {
    return x >= r.x1 && x <= r.x2 && y >= r.y1 && y <= r.y2;
    // Внимавайте със строгите неравенства (< vs <=) според условието
}

3. 2D Префиксни Суми (2D Prefix Sums)

Ако имаме матрица \(A\) с числа и множество заявки за сумата в подправоъгълник \((x_1, y_1)\) до \((x_2, y_2)\), можем да отговаряме за \(O(1)\) след препроцесинг \(O(N \cdot M)\).

Препроцесинг

Създаваме матрица pref, където pref[i][j] пази сумата на правоъгълника от \((1, 1)\) до \((i, j)\). Формула (включване-изключване): pref[i][j] = matrix[i][j] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1]

Заявка

Сумата в правоъгълник, дефиниран от \((r1, c1)\) (горе-ляво) и \((r2, c2)\) (долу-дясно): Sum = pref[r2][c2] - pref[r1-1][c2] - pref[r2][c1-1] + pref[r1-1][c1-1]

// Примерна имплементация (1-based index)
vector<vector<long long>> pref(N + 1, vector<long long>(M + 1, 0));
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
        pref[i][j] = matrix[i][j] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
    }
}
// Заявка за (r1, c1) до (r2, c2)
long long query(int r1, int c1, int r2, int c2) {
    return pref[r2][c2] - pref[r1-1][c2] - pref[r2][c1-1] + pref[r1-1][c1-1];
}

4. Компресия на координати (Coordinate Compression)

Ако координатите са големи (напр. до \(10^9\)), но броят на правоъгълниците \(N\) е малък (напр. \(1000\)), не можем да създадем матрица с размер \(10^9 \times 10^9\). Но реално важните координати са само тези, където започва или свършва правоъгълник (\(x_1\) и \(x_2\)). Има най-много \(2N\) уникални X и \(2N\) уникални Y координати.

Алгоритъм:

  1. Съберете всички \(x\) координати във вектор xs.
  2. Сортирайте xs и премахнете дубликатите (sort + unique).
  3. Заменете всяка координата \(x\) от входа с нейния индекс в xs (чрез lower_bound).
  4. Сега работите с координати в интервала \([0, 2N]\).
vector<int> xs;
for (auto r : rects) { xs.push_back(r.x1); xs.push_back(r.x2); }
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());

// Get compressed value
int compressed_x = lower_bound(xs.begin(), xs.end(), raw_x) - xs.begin();
// Get original value
int original_x = xs[compressed_x];

Това е ключова техника при работа със SegTree или Sweep Line върху големи координати.

5. Задачи

  1. CSES Forest Queries: Класическа задача за 2D префиксни суми.
  2. Codeforces 1195C: Basketball Exercise (има геометрични вариации).
  3. IOI 2013 Dreaming: Включва работа с метрики.

Съвет: Винаги рисувайте случаите, когато правоъгълниците не се пресичат, за да разберете формулите за max и min при сечението.

6. Въртене на правоъгълник (Rotation)

Ако правоъгълникът не е axis-aligned (страните не са успоредни на осите), задачите стават значително по-сложни. Често се налага: * Използване на линейна алгебра (матрици за трансформации). * Проверка за сечение чрез Separating Axis Theorem (SAT).

За основни задачи с въртене на 90°/180°/270°: 

// Въртене на точка (x, y) с 90° около началото
pair<int,int> rotate90(int x, int y) {
    return {-y, x};
}

7. Минимална ограждаща кутия (Bounding Box)

Ако имаме множество от точки, най-малкият axis-aligned правоъгълник, който ги съдържа, се намира лесно: 

Rect boundingBox(vector<Point>& points) {
    int minX = INT_MAX, minY = INT_MAX;
    int maxX = INT_MIN, maxY = INT_MIN;

    for (auto& p : points) {
        minX = min(minX, p.x);
        minY = min(minY, p.y);
        maxX = max(maxX, p.x);
        maxY = max(maxY, p.y);
    }

    return {minX, minY, maxX, maxY};
}

8. Проблеми с точност при координати

Ако координатите са реални числа (double), внимавайте с проверките за равенство: 

const double EPS = 1e-9;

bool areEqual(double a, double b) {
    return abs(a - b) < EPS;
}

При работа с цели координати (\(10^9\)), площта може да достигне \(10^{18}\), което се побира в long long. Но при още по-големи координати може да се наложи BigInt или модулна аритметика.

9. Разширени задачи

9.1. Площ на обединение на \(N\) правоъгълника

За това се използва Sweep Line алгоритъм (вижте Тема 27): * Събираме всички вертикални ръбове (откриващи и затварящи). * Сортираме ги по X координата. * Поддържаме активни интервали по Y оста чрез Segment Tree или друга структура.

Сложност: \(O(N \log N)\).

9.2. Брой точки в правоъгълник (Range Query 2D)

Ако имаме \(M\) заявки за брой точки в даден правоъгълник: * Офлайн метод: Използваме Sweep Line + Fenwick Tree. * Онлайн метод: 2D Range Tree или Fractional Cascading.

🏁 Заключение

Работата с правоъгълници е основна в много области на състезателното програмиране. Владеенето на: * Формулите за сечение и обединение. * 2D префиксни суми. * Компресия на координати.

...ще ви позволи да решавате широк спектър от геометрични и оптимизационни задачи. Винаги тествайте с ръбни случаи (правоъгълници, които споделят само един връх, напълно припокриващи се и т.н.).