Как найти общую площадь двух прямоугольников

S = a * b

——————

а)

1) 175 * 28 = 4 900 см² — площадь первого прямоугольника

2)   175 * 72 = 12 600 см² — площадь второго

3) 4 900 + 12 600 = 17 500 см² — площадь двух прямоугольников

или можно обойтись без вычисления площади каждого прямоугольника, т.к. длина одинаковая:

175 * (28 + 72) = 175 * 100 = 17 500 см²

б)

1) 73 * 91 = 6 643 см² — площадь первого прямоугольника

2) 27 * 91 = 2 457 см² — площадь второго

3) 6 643 + 2 457 = 9 100 см² — площадь двух прямоугольников

или:

91 * (73 + 27) = 91 * 100 = 9 100 см².

1 ответ:

Читайте также

A Swift-version solution with analysis and LeetCode test results.

/**
 Calculate the area of intersection of two given rectilinear rectangles.

 - Author:
 Cong Liu <congliu0704 at gmail dot com>

 - Returns:
 The area of intersection of two given rectilinear rectangles.

 - Parameters:
 - K: The x coordinate of the lower left point of rectangle A
 - L: The y coordinate of the lower left point of rectangle A
 - M: The x coordinate of the upper right point of rectangle A
 - N: The y coordinate of the upper right point of rectangle A
 - P: The x coordinate of the lower left point of rectangle B
 - Q: The y coordinate of the lower left point of rectangle B
 - R: The x coordinate of the upper right point of rectangle B
 - S: The y coordinate of the upper right point of rectangle B

 - Assumptions:
 All the eight given coordinates (K, L, M, N, P, Q, R and S) are integers
 within the range [-2147483648...2147483647], that is, Int32-compatible.
 K < M, L < N, P < R, Q < S

 - Analysis:
 The area of intersected is dyIntersected * dxIntersected.

 To find out dyIntersected, consider how y coordinates of two rectangles relate
 to each other, by moving rectangle A from above rectangle B down.

 Case 1: when N >  L >= S >  Q, dyIntersected = 0
 Case 2: when N >= S >  L >= Q, dyIntersected = S - L
 Case 3: when S >  N >  L >= Q, dyIntersected = N - L
 Case 4: when S >= N >= Q >  L, dyIntersected = N - Q
 Case 5: when N >  S >  Q >  L, dyIntersected = S - Q
 Cases 2 and 3 can be merged as Case B:
         when           L >= Q, dyIntersected = min(N, S) - L
 Cases 4 and 5 can be merged as Case C:
         when           Q >  L, dyIntersected = min(N, S) - Q
 Cases B and C can be merged as Case D:
         when      S >  L     , dyIntersected = min(N, S) - max(L, Q)

 Likewise, x coordinates of two rectangles relate similarly to each other:
 Case 1: when R >  P >= M >  K, dxIntersected = 0
 Case 2: when      M >  P     , dxIntersected = min(R, M) - max(P, K)

 - Submission Date:
 Sat 20 Jan 2018 CST at 23:28 pm

 - Performance:
 https://leetcode.com/problems/rectangle-area/description/
 Status: Accepted
 3081 / 3081 test cases passed.
 Runtime: 78 ms
 */
class Solution {
  public static func computeArea(_ K: Int, _ L: Int, _ M: Int, _ N: Int, _ P: Int, _ Q: Int, _ R: Int, _ S: Int) -> Int {
    let areaA : Int = Int((M - K) * (N - L))
    let areaB : Int = Int((R - P) * (S - Q))
    var xIntersection : Int = 0
    var yIntersection : Int = 0
    var areaIntersection : Int = 0

    if ((min(M, R) - max(K, P)) > 0) {
      xIntersection = Int(min(M, R) - max(K, P))
    }

    if ((min(N, S) - max(L, Q)) > 0) {
      yIntersection = Int(min(N, S) - max(L, Q))
    }

    if ((xIntersection == 0) || (yIntersection == 0)) {
      areaIntersection = 0
    } else {
      areaIntersection = Int(xIntersection * yIntersection)
    }

    return (areaA + areaB - areaIntersection)
  }
}

// A simple test
Solution.computeArea(-4, 1, 2, 6, 0, -1, 4, 3) // returns 42

Алгоритм поиска площади нескольких прямоугольников

Здравствуй, Хабр. Во время похождения по итернетам в поисках годного алгоритма на эту тему я увидел одну интересную идею, которую на досуге развил и дополнил. Наверное, каждый более-менее опытный кодер встречал типовую задачу на пресечение нескольких прямоугольников в системе координат. Насколько я понял, вопрос годного алгоритма остается открытым, а потому я решил предложить свой.

Давайте возьмем гипотетическую задачу:

Существует система координат, в которой расположено N-ное количество прямоугольников, параллельных осям координат, которые заданы координатами левой нижней и правой верхней вершины прямоугольника. Требуется найти общую площадь, занимаемую прямоугольниками.

• Первым делом требуется создать 2 массива, один одномерный, другой двумерный. В первом массиве мы будем хранить координаты всех точек, второй будет представлять собой координатную плоскость
• Так же, нам надо запомнить самую маленькую и самую большую координату по оси ординат. Тоже и с осью абсцисс. Этими точками мы задаем размеры второго массива. Это нам надо для того, чтобы убедиться, что область, которую мы будем рассматривать (назовем ее областью А), полностью покрывает нашу зону интереса, что является необходимым и достаточным условием.
• Следом, мы проецируем прямоугольники на область А, т.е. координаты прямоугольников будут эквивалентны номерам некоторым элементам массива со смещением.
• Затем начинаем заполнять этот массив. Элементы этого массива могут принимать два значения: 0 и 1. 0 означает, что это «клеточка» не принадлежит ни одному прямоугольнику, 1- принадлежит. Проверяем элементы области А на принадлежность прямоугольнику для каждого отдельного прямоугольника. 1 не может быть заменен на 0. 0 может быть заменен на 1. Таким образом, мы получим матрицу, которая будет состоять из нулей и единиц, где единицами будут «нарисованы» прямоугольники.
• Последним пунктом, считаем сумму всех элементов массива. Задача решена!

В заключение статьи хотелось бы рассказать об плюсах и минусах данного алгоритма.

Плюсы:

— Скорость работы при прочих равных напрямую зависит от количества данных прямоугольников и их разброса.
— Нет кучи условных операторов, которые сильно портят жизнь.
— Не надо отслеживать пересечения прямоугольников, те «клетки», которые принадлежат двум или более прямоугольникам все равно будут посчитаны только 1 раз.
— Высокая читаемость кода (при достаточно прямых руках).
— Простота реализации.
— Одинаковый алгоритм обработки для всех частей координатной плоскости.

Минусы:

— Требует достаточно хорошего пространственного воображения.
— Наличие достаточно большого количества циклов.
— Не подходит для большинства задач даже с незначительно измененными условиями.