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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ сортировка в алфавитном порядке пофамилии/году рождения http://www.cyberforum.ru/cpp-beginners/thread608799.html
В файле input.xtx содержатся сведения о группе студентов в формате: запись о каждом студенте группы, которая содержит следующие сведения:фамилия, имя, отчество, год рождения, оценки по пяти предметам. Переписать данные файла input.txt в output.txt, отсортировав их: в алфавитном порядке по фамилии, а затем по убыванию года рождения. Желательно методом вставок или методом пузырька. Исходный...
C++ объединенная матрица помогите найти ошибку в программе #include <cstdlib> #include <iostream> #include <fstream> #include <math.h> using namespace std; int main() {double ka,kb,tempa,tempb; http://www.cyberforum.ru/cpp-beginners/thread608795.html
C++ Программа останавливается без ошибок на fopen
Добрый вечер. Программа останавливается без ошибок или сообщений дебагера на строчке 190. Помогите разобраться, что не так. Код написан в С++ Builder Ниже прикрепил два файла: *Магазины *Продукты //--------------------------------------------------------------------------- #include <vcl.h> #include <stdio.h>
Пишу консольное приложение C++
Здравствуйте. Решил написать программу, идея программы заключается в том чтобы на базе консольного приложения написать программу(функции ввода вывода, изменения цвета, скроллинг видимого буфера консоли). Программа будет пользователем получать команды, и исполнять функции, но этот функционал должен подключаться в виде библиотек dll. Для библиотек будет выделена соответствующая папка в директории с...
C++ Хелпуйте! Надо написать функцию! http://www.cyberforum.ru/cpp-beginners/thread608744.html
Написать функцию, которая устанавливает месяц и число по порядковому номеру дня, переданного ей в качестве параметра.
C++ Создал прогу в С++, я нуб, проверте меня, и поставте оценку Дан целочисленный массив A(n) с элементами, сгенерированными случайными числами в диапазоне (-20, 20). Требуется: Отсортировать по убыванию положительные элементы массива методом выбора. #include<iostream.h> #include<conio.h> #include<stdlib.h> void sort (int k,int); void main() { int i,j,n,k,x,b; clrscr(); gotoxy(29,4); подробнее

Показать сообщение отдельно
Sergfut
0 / 0 / 0
Регистрация: 18.06.2012
Сообщений: 20
19.06.2012, 19:56  [ТС]     Вычислить периметр пересекающихся прямоугольников
Количество их не произвольное,и ориентированны они произвольно.

Добавлено через 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 секунд
Вот немного теории и решения данной задачи на паскале....только я вообще не могу понять что тут да и как делать.......
 
Текущее время: 04:40. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru