5 Способ 1 — прямоугольник и формула
Способ 1 — прямоугольник и формула
Число точек с целочисленными координатами внутри прямоугольника со сторонами a и b (включая границу) равно:
(a + 1) · (b + 1)
Почему «+1»: вдоль стороны длины a стоит a клеток, но a + 1 узлов (границы считаем с обоих концов).
Чтобы посчитать объединение двух прямоугольников:
1. Найди число точек в каждом: (a₁+1)(b₁+1) и (a₂+1)(b₂+1).
2. Найди прямоугольник-пересечение (наложение по x и по y) и посчитай точки в нём.
3. Подставь в формулу: Объединение = A + B − Пересечение.
📌 Как найти пересечение прямоугольников Пересечение по оси — это перекрытие отрезков. Если фигура A занимает по x отрезок [0; 6], а B — [4; 10], то их общий отрезок по x — [4; 6] (от большего левого до меньшего правого). Так же по y. Пересечение узлов = (перекрытие по x + 1) · (перекрытие по y + 1). |