Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Sergfut
0 / 0 / 0
Регистрация: 18.06.2012
Сообщений: 20
#1

Вычислить периметр пересекающихся прямоугольников - C++

19.06.2012, 19:12. Просмотров 890. Ответов 2
Метки нет (Все метки)

Помогите написать,описание и реализация алгоритма вычисления периметра пересекающихся прямоугольников.На С++.
Заранее благодарю!

Добавлено через 21 час 21 минуту
Добрые люди откликнитесь....
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.06.2012, 19:12
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Вычислить периметр пересекающихся прямоугольников (C++):

Найти периметр и площадь пяти прямоугольников по известным сторонам - C++
Вот условие: Найти периметр и площадь пяти прямоугольников по известным сторонам. #include <stdio.h> int pr(float a,float b,...

Вычислить интеграл методом прямоугольников - C++
Ребят помогите пожалуйста кому не трудно :( Вычислить интеграл методом прямоугольников. Начальное число шагов численного интегрирования –...

Вычислить интеграл f(x)=5x(кв.)-x+2 методом прямоугольников - C++
Напишите программу вычисления интеграла f(x)=5x(кв.)-x+2 методом прямоугольников

Вычислить периметр треугольника - C++
Даны координаты трех вершин треугольника A(x 1,y 1), B(x 2,y 2) и С(x 3,y3). Вычислить периметр треугольника. Для вычислений воспользуйтесь...

Вычислить периметр пятиугольника - C++
Пожалуйста, помогите сделать задание на C++ :) Пользователь вводит длину сторон пятиугольника, каждая сторона заносится в массив. ...

Вычислить периметр треугольника - C++
Вычислить периметр произвольного треугольника, если известны две его стороны и угол между ними.

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Root2x
12 / 12 / 0
Регистрация: 21.05.2012
Сообщений: 52
19.06.2012, 19:20 #2
Скажите пожалуйста, сколько прямоугольников? А так же ориентированны они по осям или нет?
Sergfut
0 / 0 / 0
Регистрация: 18.06.2012
Сообщений: 20
19.06.2012, 19:56  [ТС] #3
Количество их не произвольное,и ориентированны они произвольно.

Добавлено через 21 минуту
Дано N (0<JV<5000) прямоугольников со сторонами, па-
раллельными координатным осям. Каждый прямоугольник мо-
жет быть частично или пол-
ностью перекрыт другими
прямоугольниками. Вершины
всех прямоугольников имеют
целочисленные координаты в
пределах [-10000, 10000] и
каждый прямоугольник име-

1
252 5. Алгоритмы вычислительной геометрии
ет положительную площадь.
Периметром называется об-
щая длина внутренних и
внешних границ фигур, полу-
ченных путем наложения
прямоугольников. Найти зна-
чение периметра.
На рисунке показана фигура из 7 прямоугольников. Соот-
ветствующие границы полученной фигуры показаны на следу-
ющем рисунке.
Пример входного файла:
7 (количество прямоугольников)
-15 0 5 10 (границы прямоугольника — нижняя левая и верх-
няя правая)
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
Ответ: 228.
Рассмотрим более простую задачу. На прямую «набросали»
какое-то количество отрезков. Последние могут пересекаться,
находиться один внутри другого и т. д. Требуется определить
количество связных областей, образованных этими отрезками.
На рисунке даны три отрезка
(2, 5), (4, 6) и (8,10). Количест- ^ l l l l I
во связных областей две. Как j 4 5 6 8 10
их найти? Используем стан-
дартный прием. Записываем в
один массив координаты отрезков, в другой признаки начала
(1) и конца отрезков (-1). Сортируем элементы первого массива
по неубыванию, одновременно переставляя соответствующие
элементы второго массива. После этого осталось считать сумму
значений признаков. Если ее текущее значение равно нулю, то
выделена очередная связная область.
Вернемся к исходной задаче. Очевидно, что можно считать
периметр отдельно, по частям. Например, первоначально его
составляющую по оси Y, а затем по оси X. Рассмотрим идею
решения на примере (рисунок). Даны четыре прямоугольника.
Считаем составляющую периметра по оси Y. Ось разбивается
координатами прямоугольников на следующие участки: (0,1),
(1,2), (2,3), (3,4) и (4,6). Рассматриваем каждый участок, т. е.
5. Алгоритмы вычислительной геометрии 253
4.,
2:(5,0МВ,2)
3:(7,1И9,4)
4:(4,ЗИЮ,6)
10
определяем прямоуголь-
ники (точнее их коорди-
наты по X с признаками
начала и конца интерва-
ла), которые могут дать
«вклад» в периметр. Для
первого участка — один
прямоугольник, для вто-
рого — три, для третье-
го — два, для четверто-
го — три и для пятого —
один. Выписав для каждого участка координаты X с соответст-
вующими признаками, выполняем сортировку и находим коли-
чество связных областей. Так, на рисунке для первого сечения
(отмечено цифрой 1) количество связных областей равно 1, а
для второго сечения — 2. После этого достаточно длину этого
участка умножить на количество связных областей и удвоить
результат. Получаем составляющую периметра по оси У на
этом участке.
После этих замечаний можно приступить к разбору реше-
ния. Как обычно, начинаем со структур данных.
Const MaxN=5001/
Type MasPn=Array[1..MaxN*2] Of Integer;
MasSw=Array[l..MaxN*2, 1..2] Of Integer;{*Для
записи координат и соответствующих
признаков начала и конца отрезков.*}
Var N, i: Integer;
Ах, Ay: MasPn;{*Для хранения координат
прямоугольников. *}
Основная программа.
Begin
Assign (Input, '...') /Reset (Input) /Read (N) /
For i:=l To N Do Begin Read (Ax [ i*2-l ] ,
Ay [i* 2-1] ) /Read(Ax[i*2] , Ay[i*2]); End/
Close (Input)/
Assign (Output, '...') /Rewrite (Output) /
WriteLn(GetPerim(Ax, Ay) + GetPerimfAy, Ax));
Close(Output);
End.
Вспомогательную процедуру сортировки по любому методу с
временной оценкой O(N*logN) описывать не будем.
254 5. Алгоритмы вычислительной геометрии
Procedure Sort(Var nn: MasSw; If, rg: Integer) ;
Begin
End;
Функция GetPerim.
Function GetPerim (Const Ax, Ay: MasPn): Longlnt;
Var i: Integer;
sc: Longlnt;
D: MasSw;
Begin
sc:=0;{*Значение периметра по одному из
направлений. *}
FillChar(D, SizeOf (D) , 0) ;
For i:=l To 2*N Do D[i, 1 ] :=Ax [i] ; { *Массив
координат по этому направлению. *}
Sort(D, 1, 2*N) ;{*Сортировка . *}
For i:=l To N*2-l Do
IfD[i, !]<>D[i+l, 1] Then{*'Если координаты не
равны, то вычисляем количество связных
областей на этом сечении - функция GetPr,
умножаем на длину участка и на 2.*}
sc:=sc+GetPr(Ax, Ay, D[i, 1]) * (D[i+1, 1] -
D[i, 1]) * 2;
GetPerim:=sc;
End;
Следующий шаг уточнения. Вычисляем количество связных
областей на сечении, определяемом значением переменной х.
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
Function GetPr(Const Ax, Ay: MasPn; x: Integer):
Integer;
Var i, b, d, sc: Integer;
nn: ^MasSw;{*Число прямоугольников многовато
(до 5000), задействуем «кучу». *}
Begin
New (nn) ;
GetRect(Ax, Ay, x, ппл, sc);{*Определяем
прямоугольники, имеющие отношение к
рассматриваемому сечению, их количество -
значение переменной sc, а координаты в
массиве nn*. *}
If sc<>0 Then Sort (ппл, 1, sc);{*Выполняем
сортировку с одновременной перестановкой
признаков начала и конца отрезков. *}
5. Алгоритмы вычислительной геометрии 255
Ъ:=0/{*Для хранения суммы значений признаков. *}
If sc>0 Then d:=l Else d:=0;
For i:=l To sc-1 Do Begin
b:=b+nn~[i, 2];
If (b=0) And (nn*[i+l, 1]<>ппл[1, 1]) Then Inc (d) ;
{*Если текущее значение b равно нулю и
координаты не совпадают, то увеличиваем
счетчик числа связных областей. *}
End;
GetPr:=d;
Dispose(nn);
End;
Последний шаг уточнения логики — определение характе-
ристик сечения.
Procedure GetRect (Ax, Ay: MasPn; x: Integer;
Var nn: MasSw;Var sc: Integer);
Var i: Integer;
Begin
sc:=0;
For i:=1 To N Do
If (Ax[i*2-l]<=x) And (x<Ax[i*2]) Then Begin
{*Если прямоугольник имеет отношение
к сечению, то запоминаем координаты
по соответствующему направлению (они
в массиве Ау) и признаки начала
и конца отрезка. *}
Inc (sc) ;
nn[sc, 1]:=Ay[i*2-l];nn[sc+l, 1]:=Ay[i*2];
nn[sc, 2]:=1;nn [sc+1, 2]:=-l;
Inc (sc);
End;
End;
Добавлено через 50 секунд
Вот немного теории и решения данной задачи на паскале....только я вообще не могу понять что тут да и как делать.......
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.06.2012, 19:56
Привет! Вот еще темы с ответами:

Вычислить определенный интеграл методом прямоугольников - C++
Вычислить определенный интеграл методом прямоугольников Помогите!!! Вообще не пойму как делать?

Вычислить интеграл методами прямоугольников и Симпсона - C++
Разработать алгоритм блок-схемы, чтобы обчислить численного интегрирования с использованием метода прямоугольника или Симпсона

Вычислить площадь и периметр четырехугольника - C++
помогите пожалуйста программу на с++6.0.,которая бы выбирала из предложенных четырехугольников один из них, а потом вводились бы стороны,...

Вычислить площадь и периметр круга - C++
Доброго времени суток, форумчане. Просьба помочь с простыми программами на С++. Только начал изучать, но путаюсь, где какой оператор и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru