Вопрос № 60301: Здравствуйте!
Помогите плз, что называется, как можете. Теряюсь в мыслях и не знаю как подойти к задаче. Зарание здоровенное спасибо!
Задача:
Дано n (2<n<20) прямоугольников, стороны которых параллельны осям координат. Кажд...
Вопрос № 60.301
Здравствуйте!
Помогите плз, что называется, как можете. Теряюсь в мыслях и не знаю как подойти к задаче. Зарание здоровенное спасибо!
Задача:
Дано n (2<n<20) прямоугольников, стороны которых параллельны осям координат. Каждый прямоугольник характирезуется кординатами верхнего левого и ему противополжного углами.
Прямоугольники могут пересекаться. Если они пересекаются, то их пересечением может быть одна точка, отрезок или прямоугольник (в некоторых случаях квадрат). Напишите прогу, которая определила бы пересечение прямоугольников , если оно существует.
Начальные данные читаются из файла dano.txt. На первой строчке написано число n. В остальных n строчках написано по четыре целых числа из интервала [-1000; 1000], разделенных пробелами: первое число – х координата верхнего левого угла прямоугольника, второе – тогоже угла у координата, третье – противоположного угла x координата, четвертое – противоположного угла у координата.
Результат заносится в файл rez.txt.
Если не пересикаются, пишется НЕ ПЕРЕСЕКАЮТСЯ.
Если пересекаются в точке, пишется ТОЧКА_х_у (координаты)
Если место пересечения отрезок, пишется ОТРЕЗОК, координаты точки,верхнего или левого конца отрезка (x ir y) и координаты другого конца отрезка (x, y). Все числа, просто, через пробел.
Если площадь пересечения квадрат или прямоугольник: пишется КВАДРАТ или ПРЯМОУГОЛЬНИК, координаты верхнего левого угла и координаты противоположного угла, через пробел.
Приложение:
Отправлен: 26.10.2006, 22:32
Вопрос задал: Dr1m (статус: Посетитель)
Всего ответов: 1 Мини-форум вопроса >>> (сообщений: 0)
Отвечает: Сухомлин Кирилл Владимирович
Здравствуйте, Dr1m!
Кроме того, что числа означают координаты вершин, они означают координаты сторон. И если порисовать пересекающихся (и не только) прямоугольников, то можно заметить, что при пересечении двух прямоугольников левая сторона имеет горизонтальную координату максимальной из координат левых сторон этих двух прямоугльников. И аналогично для остальных сторон. Т.е. для прямоугольников:
(x1a, y1a, x2a, y2a)
(x1b, y1b, x2b, y2b)
пересечением будет:
(max(x1b,x1a), max(y1b,y1a), min(x2b,x2a), min(y2b,y2a))
На всякий случай напомню, что в программировании ось Oy направлена вниз.
Остается осознать два факта:
1) Эта формула верна для любого кол-ва прямоугольников (тогда функции надо брать на всех интервалах)
2) (x1 > x2) или (y1 > y2) тогда и только тогда, когда пересечение пустое.
Здесь x1=max(x1a, x1b, ...) x2=min(x2a, x2b, ...) и аналогично для y.
Итого:
1. Прочитать данные в 4 массива (или в один двумерный)
2. Найти на них максимумы/минимумы и записать это в 4 переменных
3. На основе сравнения этих переменных выдать ответ.
Последний пункт я вам даже в виде кода приведу (см. приложение)
Разумеется, там надо еще добавить разделители между числами при выводе и вообще, всю программу написать. Но я итак достаточно подробно все разжевал.
ЗЫ: У нас была точно такая же задача на какой-то олимпиаде по программированию. Совершенно не помню, ни класс, (9,10,11), ни этап (рай., гор., обл.) Хотя по сложности тянет на районную. Даже для 9-го.
Приложение:
--------- Не узнаешь - не попробуешь.
Ответ отправил: Сухомлин Кирилл Владимирович (статус: Практикант)
Ответ отправлен: 27.10.2006, 02:24 Оценка за ответ: 5 Комментарий оценки: Очень доходчево_объяснили, спасибо
