Как найти площадь пересечения двух прямоугольников?
Есть два прямоугольника стороны, которых параллельны осям и они пересекаются. Нам известно: (x1,y1) — левая нижняя точка первого прямоугольника (x2,y2) — правая верхняя точка первого прямоугольника (x3,y3) — левая нижняя точка второго прямоугольника (x4,y4) — правая верхняя точка второго прямоугольника И нужно найти площадь их пересечения. Но пересекатся они могут с разних сторон.
Отслеживать
13.7k 12 12 золотых знаков 43 43 серебряных знака 75 75 бронзовых знаков
задан 14 дек 2017 в 21:45
Oleksii Havryshkiv Oleksii Havryshkiv
111 1 1 золотой знак 1 1 серебряный знак 12 12 бронзовых знаков
@Igor просто у меня есть много прямоугольников которие нужно перебирать одни с другими. И не могу понять как найти площадь пересечения каждого с каждим. Как их перебратить и пересекаются ли они я знаю. А вот етого понять не могу. Так как ети прямоугольники могут пересекатся с разних сторон. Если знаете, то помогите пожалуйста
14 дек 2017 в 21:52
Можно для обоих найти общий прямоугольник, а затем умножить его ширину на высоту.
14 дек 2017 в 21:56
@VladimirGamalyan да ну как найти нужное нам пересечение.
14 дек 2017 в 21:58
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
Хотя вопрос и простой, оставлю в качестве шпаргалки-сниппета:
#include /* x1, y1 - левая нижняя точка первого прямоугольника x2, y2 - правая верхняя точка первого прямоугольника x3, y3 - левая нижняя точка второго прямоугольника x4, y4 - правая верхняя точка второго прямоугольника */ int f(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4)
Исходя из вопроса, полагаю, что координаты растут из нижнего левого угла (если же Y растет сверху вниз, то необходимо внести соответствующие поправки).
Идея простая, иллюстрируется на картинке (показано как определяется ширина общего прямоугольника, высота определяется аналогично):
Алгоритм нахождения площади пересечения
Вот задача, но мне не нужен код, помогите с алгоритмом нахождения площади пересечения.
Напишите программу, которая находит площадь пересечения, то есть общей части двух прямоугольников. Каждый прямоугольник задается координатами двух произвольных противоположных углов. Стороны прямоугольников параллельны осям координат.
Ваша программа должна вводить с клавиатуры числа x1, y1, x2, y2, x3, y3, x4, y4. Числа xi, yi будут вводиться в i-строке (1≤i≤4) и разделяться одним пробелом. Точки (x1, y1) и (x2, y2) – координаты двух противоположных углов первого прямоугольника. Точки (x3, y3) и (x4, y4) – координаты двух противоположных углов второго прямоугольника.
Числа xi, yi – целые; 0≤xi, yi≤30000; оба прямоугольника имеют ненулевую площадь.
Ваша программа должна вывести на экран одно число S – площадь общей части двух введенных прямоугольников. Если введенные прямоугольники не имеют общих точек, то ваша программа должна вывести на экран число 0.
Голосование за лучший ответ
собственно, всё сводится к нахождению пересечений отрезков (x1, x2) ∩ (x3, x4) и отрезков (y1,y2) ∩ (y3, y4)
а пересечение отрезков (a, b)∩(c, d) посчитать легко: это (max(a,c), min(b,d)).
если max(a,c) > min(b,d), то пересечение пустое
так что программа простая:
1) приводишь прямоугольники (xi, yi) — (xj, yj) к «нормальному» виду
xi < xj, yi < yj
2) находишь пересечения отрезков
(x1, x2) ∩ (x3, x4) = (xA, xB)
(y1, y2) ∩ (y3, y4) = (yA, yB)
3) если пересечения не пустые, считаешь площадь прямоугольника (xA, yA) — (xB, yB)
Задача по Python 3.6?
На плоскости даны два прямоугольника, каждый прямоугольник задан координатами левого нижнего и правого верхнего угла. Найдите площадь пересечения этих прямоугольников.
ВХОДНЫЕ ДАННЫЕ
Программа получает на вход 8 чисел. Сначала даны координаты левого нижнего угла первого прямоугольника . Затем даны координаты правого верхнего угла первого прямоугольника . Затем аналогично даны координаты второго прямоугольника и .
Числа заданы по одному числу в строке, −10000⩽x1
ВЫХОДНЫЕ ДАННЫЕ
Программа должна выводить одно целое число – площадь пересечения данных прямоугольников.
- Вопрос задан более трёх лет назад
- 3107 просмотров
Комментировать
Решения вопроса 1
ban_by_fb @ban_by_fb Автор вопроса
x1=int(input())
y1=int(input())
x2=int(input())
y2=int(input())
x3=int(input())
y3=int(input())
x4=int(input())
y4=int(input())
# границы области пересечения
left = max(x1, x3) # левая
bottom = max(y1, y3) # нижняя
right = min(x2, x4) # правая
top = min(y2, y4) # верхняя
width = right — left # ширина пересечения
height = top — bottom # высота пересечения
# если ширина и высота области пересечения меньше или равны 0
if width # то его площадь 0
—-print(0)
else:
# если больше 0, то выводим площадь
—-print(width * height)
вместо — ставить пробелы
Как найти пересечение прямоугольников по координатам
standoff → Еhis isn’t fair.
maomao90 → I am top 1 contributor. AMA!
arham_doshi → cses graph session editorial(incomplete)
SAD_IN_NIGHTMARE → 2024 OIs
MikeMirzayanov → Codeforces Single Account Policy: zh0ukangyang is Removed from the Rating
mohammed_orkhan → I wnat to be EXPERT!!
parth_1818 → Know Some Sorting Techniques
stefdasca → Easy and Quick Video Tutorials for the CSES Problem Set
maomao90 → Editorial for Hello 2024
I_am_Polish_Girl → Dijkstra Algorithgm
atcoder_official → AtCoder Beginner Contest 335 (Sponsored by Mynavi) Announcement
awoo → Разбор Educational Codeforces Round 149
Vectrizz → Золотой расчет: оптимизация ценности в рюкзаке с умением раздробить слитки!
Hexagons → [OFF TOPIC] Hollow Knight radiant tutorial for bossfight «Markoth»
pajenegod → The Ultimate Reroot Template
CheaterExposer → [UPDATE] Codeforces Cheater IOI Medalist
triumphh → What rating on codeforces should I aim for to crack ZCO and INOI?
sahal → CSES Problemset Editorials (almost all section editorial collection)
Zlobober → Checkers with testlib.h
oversolver → Expert for the first time since 2011, AMA
Algorithms_with_Shayan → How to approach DP problems & DP playlist
Nurali16 → tourist is not noob . he is genius
AminAnvari → Segment Tree Problems
P etr → A 1:1 week
TurtleZW → Codeforces Round #828 (Div. 3)