Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Помогите решить задачу на паскале!!! / 20 сообщений из 20, страница 1 из 1
29.11.2006, 22:44
    #34165620
sonomeD
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
Здраствуйте, господа.Очень нужна помощь в решении задачи:
Дано N прямоугольников, стороны которых паралельны осям координат.
Найти площадь, которую занимают эти прямоугольники.
Входящие данные(файл Priam.in):
В первой строке находится N.(N<=3000)
Далее в следующих N строках находятся координаты левого верхнего и правого нижнего угла каждого прямоугольника(координаты - целые числа в пределах от 0 до 1000000).
Исходящие данные(файл Priam.out):
В исходящий файл записать одно число - площадь покрытую прямоугольниками. Результат записать с тремя знаками после запятой.
Пример:
Priam.in
3
1 2 3 1
2 2 3 1
2 4 3 2
Priam.out
5.000
...
Рейтинг: 0 / 0
29.11.2006, 22:58
    #34165637
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
$400
...
Рейтинг: 0 / 0
29.11.2006, 23:02
    #34165640
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
$399

Б/П
...
Рейтинг: 0 / 0
29.11.2006, 23:05
    #34165642
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
$600 с добавлением моего копирайта в тело программы.
...
Рейтинг: 0 / 0
29.11.2006, 23:08
    #34165644
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
Твойя взяла! Пеши.
...
Рейтинг: 0 / 0
30.11.2006, 08:15
    #34165874
madvet
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
sonomeDОчень нужна помощь
Давай помогу, сколько по деньгам?
...
Рейтинг: 0 / 0
30.11.2006, 08:34
    #34165905
mikolas
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
А пересечения прямоугольников учитываются?
...
Рейтинг: 0 / 0
30.11.2006, 15:39
    #34167803
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
mikolasА пересечения прямоугольников учитываются?

за 200$ нет, а за 398$ да.
...
Рейтинг: 0 / 0
30.11.2006, 17:22
    #34168276
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
...
Рейтинг: 0 / 0
30.11.2006, 17:26
    #34168290
ZeusTheTrueGod
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
с удовольствием решаю такие задачи... тут идея следующая

1) Строится сетка, неравномерная, по количеству различных икс и различных у, то есть что то вроде[src]

Соотвественно заводится 2 одномерных массива по горизонтали и повертикали, в которых указываетя размер одного элемента сетки

2) В эту сетку (то есть в двумерный массив) "рисуются" все прямоугольники

3) Теперь можно и подсчитать площадь, зная размер каждой ячейки неравномерной сетки



Знаю и другой способ, а именно идея с тем что площадь всей фигуры - это общая площадь минус площади пересечения всех 2ух + площадь пересечений всех трёх - площадь песеечений сетырёх


Преимущество такого способа - можно и треугольники, и х угольники, и круги

недостатки - много переборов, вроде как 2 в степени n , где n - количество фигур, но можно оптимизировать.

Пишите по теме! чур готовые программы не писать или писать с небольшими ашипками ))
...
Рейтинг: 0 / 0
30.11.2006, 17:28
    #34168296
ZeusTheTrueGod
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
AndreTM Лень было гугл посмотреть? 1ый способ не оттуда! Как раз он и нужен был в той ссылке

Время работы - O(N*N) , где - N - число этих прямоугольников. Всем завидовать
...
Рейтинг: 0 / 0
30.11.2006, 17:31
    #34168310
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
AndreTM Лень было гугл посмотреть?
@#$ его знает. У студента задание немножко не так формулируется. Ему надо вычислить union всех rectangles.

А на sources - intersection.

Хотя... одно можно присобачить для вычисления другого...
...
Рейтинг: 0 / 0
30.11.2006, 18:18
    #34168496
Шогал
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
Похожая задача:
Код: plaintext
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.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
program F;
{$APPTYPE CONSOLE}
uses
  SysUtils;

const cX1 =  1 ; cX2 =  2 ; cY1 =  3 ; cY2 =  4 ;

type
  ARR = array[byte] of record
    Value : comp;
    Mode  : byte;
    Parent : byte;
  end;

var
  ARRX, ARRY : ARR;
  IX, IY : byte;
  NX, NY : byte;
  NN, I, J, K  : byte;
  SQUARE : array[ 1 .. 4 ] of array[byte] of byte;
  X1, Y1, X2, Y2 : longint;
  VIS : array[byte] of array[byte] of byte;
  P : comp;

begin
// PART  1  : We should read squares
  AssignFile(input, 'input.txt');
  Reset(input);
  AssignFile(output, 'output.txt');
  Rewrite(output);
  NN :=  0 ;
  Read(X1, Y1, X2, Y2);
  with ARRX[IX] do begin
    Value := X1;
    Mode := cX1;
    Parent :=  0 ;
  end;
  with ARRX[IX+ 1 ] do begin
    Value := X2;
    Mode := cX2;
    Parent :=  0 ;
  end;
  with ARRY[IY] do begin
    Value := Y1;
    Mode := cY1;
    Parent :=  0 ;
  end;
  with ARRY[IY+ 1 ] do begin
    Value := Y2;
    Mode := cY2;
    Parent :=  0 ;
  end;
  Inc(IX, 2 );
  Inc(IY, 2 );
// PART  2  : reading small rectangles
  Read(NN);
  for I :=  1  to NN do begin
    Read(X1, Y1, X2, Y2);
    with ARRX[IX] do begin
      Value := X1;
      Mode := cX1;
      Parent := I;
    end;
    with ARRX[IX+ 1 ] do begin
      Value := X2;
      Mode := cX2;
      Parent := I;
    end;
    with ARRY[IY] do begin
      Value := Y1;
      Mode := cY1;
      Parent := I;
    end;
    with ARRY[IY+ 1 ] do begin
      Value := Y2;
      Mode := cY2;
      Parent := I;
    end;
    Inc(IX, 2 );
    Inc(IY, 2 );
  end;
// PART  3  : Sort ARRX and ARRY
  for I :=  0  to IX- 2  do begin
    for J := I+ 1  to IX- 1  do begin
      if( ARRX[I].Value > ARRX[J].Value) then begin
        move(ARRX[I], ARRX[ 255 ], sizeof(ARRX[ 0 ]));
        move(ARRX[J], ARRX[I], sizeof(ARRX[ 0 ]));
        move(ARRX[ 255 ], ARRX[J], sizeof(ARRX[ 0 ]));
      end;
    end;
  end;
  for I :=  0  to IY- 2  do begin
    for J := I+ 1  to IY- 1  do begin
      if( ARRY[I].Value > ARRY[J].Value) then begin
        move(ARRY[I], ARRY[ 255 ], sizeof(ARRY[ 0 ]));
        move(ARRY[J], ARRY[I], sizeof(ARRY[ 0 ]));
        move(ARRY[ 255 ], ARRY[J], sizeof(ARRY[ 0 ]));
      end;
    end;
  end;
// PART  4  : Convert float coordinates to indexed
  for I :=  0  to IX- 1  do begin
    SQUARE[ARRX[I].Mode][ARRX[I].Parent] := I;
    SQUARE[ARRY[I].Mode][ARRY[I].Parent] := I;
  end;
// PART  5  : Fill visibility array
  fillchar(VIS, sizeof(VIS),  0 );
  for I := SQUARE[cX1][ 0 ] to SQUARE[cX2][ 0 ]- 1  do begin
    for J := SQUARE[cY1][ 0 ] to SQUARE[cY2][ 0 ]- 1  do begin
      VIS[I][J] :=  1 ;
    end;
  end;
  for K :=  1  to NN do begin
    for I := SQUARE[cX1][K] to SQUARE[cX2][K]- 1  do begin
      for J := SQUARE[cY1][K] to SQUARE[cY2][K]- 1  do begin
        VIS[I][J] :=  0 ;
      end;
    end;
  end;
// PART  6  : Calculate area
  for I :=  0  to IX- 2  do begin
    for J :=  0  to IY- 2  do begin
      if(VIS[I][J] =  1 ) then begin
        P := P + (ARRX[I+ 1 ].Value - ARRX[I].Value) *
                 (ARRY[J+ 1 ].Value - ARRY[J].Value);
      end;
    end;
  end;
  Write(P: 0 : 0 );
  CloseFile(output);
end.
Только там условия были немного другие - задан большой прямоугольник, из него вырезаются маленькие, нужно найти, сколько останется от большого...
...
Рейтинг: 0 / 0
30.11.2006, 19:15
    #34168669
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
sonomeD(координаты - целые числа в пределах от 0 до 1000000).
Только что обратил внимание на это.

Итак, всего координат 10^12 примерно 2^40 примерно 117Gb
Создаем файл, хранящий координатную сетку (исходник - все 0).
Загоняем в него прямоугольники (соответствующие биты = 1)
Считаем заполненное пространство.

Не кидайте в меня камнями! На современной технике это вполне возможно.
Вечером попробую посчитать время выполнения (напр., на файле в 2Gb)

2 Зеус
Завидуйте! Тьюринг был прав - все решается тупо и прямо...
...
Рейтинг: 0 / 0
30.11.2006, 20:13
    #34168779
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
AndreTM
Итак, всего координат 10^12 примерно 2^40 примерно 117Gb

Брехня!
...
Рейтинг: 0 / 0
30.11.2006, 20:22
    #34168793
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
AndreTM sonomeD(координаты - целые числа в пределах от 0 до 1000000).
Только что обратил внимание на это.

Итак, всего координат 10^12 примерно 2^40 примерно 117Gb
Создаем файл, хранящий координатную сетку (исходник - все 0).
Загоняем в него прямоугольники (соответствующие биты = 1)
Считаем заполненное пространство.

Не кидайте в меня камнями! На современной технике это вполне возможно.
Вечером попробую посчитать время выполнения (напр., на файле в 2Gb)

2 Зеус
Завидуйте! Тьюринг был прав - все решается тупо и прямо...

проще: используйте базу заполненных квадартов + тройной хеш. (4х массив) это обойдется очень дешево, не более размера исходного файла
...
Рейтинг: 0 / 0
30.11.2006, 20:26
    #34168799
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
mayton AndreTM
Итак, всего координат 10^12 примерно 2^40 примерно 117Gb

Брехня!
1 000 000 000 000 / 1024 / 1024 / 1024 / 8 примерно равно (сверху) 117
Не надо было мне писать Gb...
Просто, если взять в качестве показателя бит (1 пиксел на координатке), то
всего бит при этих условиях будет 10^12, что эквивалентно 116.415 Гигабайт информации...
...
Рейтинг: 0 / 0
30.11.2006, 20:30
    #34168806
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
Aklinпроще: используйте базу заполненных квадартов ...
Разговор уже перешел в шутки, поскольку решать задачу никто и не собирался...
Но (см.выше) ради интереса попробую, все-таки, сколько времени займет тупой перебор.
...
Рейтинг: 0 / 0
30.11.2006, 22:48
    #34168955
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
AndreTM Aklinпроще: используйте базу заполненных квадартов ...
Разговор уже перешел в шутки, поскольку решать задачу никто и не собирался...
Но (см.выше) ради интереса попробую, все-таки, сколько времени займет тупой перебор.
Ах оставьте! Зевс предложил самый удачный алгоритм. Вы-же пытаетесь рассмотреть частные случаи.

Ваш способ более похож на вычисление площадей криволинейных фигур методом Монте-Карло. Я-бы мог это понять, когда нужна не площадь, а аппрокимация площади за малое число итераций.

И уж тем более мне не нравится цифра 1000000. А если координаты будут неограничены явно и заданны в диапазонах вещественной точности? Тут уж, батенька вам будет незачот.
...
Рейтинг: 0 / 0
01.12.2006, 09:47
    #34169357
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу на паскале!!!
цыфры, как я понял, целые. значит результат будет целым.

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

далее берем прямоугольник. для каждой его точки смотрим, есть ли она в списке, если нет, добавляем.

таким образом считем количество точек.

учитывая идиотизм задачи, тестировать ее более чем за 20мегов памяти не станет, не выгодно.

аффтопитезь
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Помогите решить задачу на паскале!!! / 20 сообщений из 20, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]