Мне вот дали задание написать алгоритм, а я что-то никак не врублю:

Цитата

Прямоугольник на плоскости задается 4-мя числами: a, b, c, d - координатами его вершин. Последовательно вводятся габариты n прямоугольников. В процессе ввода находить плоскость их пересечения, не запоминая самих габаритов.

Буду благодарен за помощь

насколько я понимаю, имеются в виду только прямоугольники с вертикальными и горизонтальными сторонами

достаточно вспомнить, что пересечение нескольких множеств можно получить таким образом:
1. берем первое множество
2. находим его пересечение со вторым
3. находим пересечение результата (2) с третьим
... (и т.д.)
символически алгоритм можно записаить так:
X:=A1
X:=X&A2
X:=X&A3
...
X:=X&An
под X и A* имеются в виду прямоугольники
под & - пересечение (пересечение двух прямоугольников тоже является прямоугольником, если стороны вертикальны или горизонтальны)
таким образом, достаточно на каждом шаге знать координаты X и текущего прямоугольника...

имхо, тот, кто давал вам задание, не очень владеет математической терминологией или вы как то не точно сформулировали. Просто если все прямоугольники задаются на плоскости, то они пересекутся не по плоскости, а от силы по какому-то многоугольнику. Кроме того в начале говорится о координатах, а потом - о габаритах.

Вобщем попробуйте уточнить

Пойди туда не знаю куда...

Левиафан
Давай сюда ТОЧНУЮ формулировку (а то бред какой-то) задания. И сразу уж копию справки о вменяемости автора задания...

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

ИМХО,
maxim1000 абсолютно прав. Ну а само пересечение двух прямоугольников можно запрограммировать путем анализа вершин каждого прямоугольника на их месторасположение внутри другого.

Цитата(redrick @ 25.10.2004, 03:01)

имхо, тот, кто давал вам задание, не очень владеет математической терминологией или вы как то не точно сформулировали.

Да нет, я ее в точности переписал из методички. Так что совсем не понятно, да? Хреново.
Я вот спрошу у автора задачки и когда он обьяснит, выложу ответ. Может кому-то интересно...

Цитата(val @ 25.10.2004, 12:12)

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

Чесно говоря я не совсем понял алгоритм maxim1000 и как провести этот анализ тоже...

Цитата

я ее в точности переписал из методички

Кретинизм.

Цитата

Прямоугольник на плоскости задается 4-мя числами: a, b, c, d - координатами его вершин.

для задания прямоугольника нужны Х и У двух вершин и Х или У третьей - 5 чисел. Если же стороны параллельны осям координат - то тогда 4 числа.

Цитата

В процессе ввода находить плоскость их пересечения

пересечением ограниченных плоских фигур плоскость не может быть потому что не может быть никогда - "я не то что изобразить - представить не могу" (с) Василь Иваныч.

Попробую переформулировать задачу так чтобы она имела смысл:

УСЛОВИЕ

Цитата

Прямоугольник, стороны которого параллельны осям координат, на плоскости задается 4-мя числами: Х1, Х2, У1, У2 - координатами его вершин. Последовательно вводятся группы чисел, соответствующих координатам n прямоугольников. В процессе ввода находить координаты области их пересечения, не запоминая самих габаритов.

РЕШЕНИЕ
[code=]Пусть Хс1, Хс2, Ус1, Ус2 - координаты прямоугольника, являющегося областью пересечения на текущий момент, причем Хс1<Хс2 и Ус1<Ус2.
Вводятся координаты очередного прямоугольника Хо1, Хо2, Уо1, Уо2, причем Хо1<Хо2 и Уо1<Уо2.
Если существует область пересечения отрезков Хо1-Хо2 и Хс1-Хс2, то ее начальная точка = новому значению Хс1, конечная = новому значению Хс2. Если пересечение отрезков - одна точка, то область пересечения вырождается в отрезок. Если пересечения отрезков нет - область пересечения прямоугольников пуста, нет ее.
Точно так же поступаем с координатами по У.
Если область пересечения вырождена по обеим коордир\натам - она вырождается в точку.[/code]

Это сообщение отредактировал(а) Akina - 27.10.2004, 17:16

Народ, что-то я читаю и торможжжжжу, скажите, прямоугольники лежат в той же плоскости?

Чисто логически задача несложная. Надо запоминать точки пересечения текущей фигуры (на втором шаге будет первый прямоугльник) и очередного прямоугольника. Понятно, что для этого надо находить точки пересечения линий. Каждая сторона фигуры лежит на линии. Что-то мне подсказывает (может и ошибаюсь), что максимальное количество углов у конечной фигуры N*4, где N - количество прямоугольников. Видимо, потому что каждая сторона прямоугольника не может пересечь более двух сторон многоугольника (или совпадать с ней), грубо говоря, вместо одного угла может сделать максимум 2.
Надо хранить координаты имеющейся фигуры, далее найти точки пересечения сторон очередного прямоугольника со сторонами фигуры (если сторона не пересекает, то надо выяснить, где она проходит), запомнить новые точки.
Потом вычислить площадь уже несложно.

Так что вся сложность состоит в аккуратном рассмотрении всех случаев и в грамотной структуре данных.

Посмотри здесь

P.S.
Если стороны прямоугольника параллельны осям, то задача совсем простая, думаю, что это не так.

Цитата

В процессе ввода находить плоскость их пересечения

Поясните, кто нибудь... Я ни хрена не понимаю... Что это за пересечение такое?

Ignat
Да бред, говорю же...

Цитата(Ignat @ 27.10.2004, 14:44)

Цитата В процессе ввода находить плоскость их пересечения Поясните, кто нибудь... Я ни хрена не понимаю... Что это за пересечение такое?

Я думаю, тут элементарная описка (может и преподавателя).
Имелась в виду ПЛОЩАДЬ.

Цитата(Alex101 @ 28.10.2004, 10:20)

Имелась в виду ПЛОЩАДЬ.

Переведено дословно с украинского "площина"