Площадь фигуры,образованная окружностями. Опции

[Vardes]

Рассматриваются n лучей,проведённых в плоскости из точки О.Углы между соседними лучами равны 2pi/n.На лучах выбраны точки A1,А2..An и из этих точек как из центров проведены окружности,проходящие через точку O.Необходимо вычислить площадь фигуры,образованную всеми окружностями.
В этом как раз вся и проблема.
Все идеи свои я исчерпал.Если у вас есть свои размышления,прошу напишите их.

Вот рисунок:

М

Сообщения объеденены ... а на следюющий раз знай, что есть кнопака "правка" klem4

[volvo]

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

{
  добавляешь эти описания:
}
const
  divider = 500;
  delta = 1/ divider;
var
  sum, none: longint;
  {
    ... и все остальные
  }

begin
{
  Здесь - все, что касается нахождения minx, miny, maxx, maxy,
  как и было раньше... А вот дальше:
}
  sum:=0; none := 0;
  tm_s:= MemL[$0040:$006c]; { контроль времени - начали отсчет }

  point_x := minx;
  while point_x <= maxx do begin

    point_y := miny;
    while point_y <= maxy do begin

      i := 1; found := False;
      While (i <= n) and not found do begin
        If Sqrt(sqr(point_x-x[i])+sqr(point_y-y[i]))<=mas[i] then found:=true
        else inc(i);
      end;
      if found then sum:=sum+1 else none := none+1;

      point_y := point_y + delta;
    end;

    point_x := point_x + delta;
  end;

  tm_f:= MemL[$0040:$006c]; { отсчет окончен }
  tm_f:=tm_f - tm_s; { замеряем время }

  writeln('time: ', tm_f);
  writeln('Внутри: ', sum, ' снаружи: ', none);
  S2:=S1*(sum/(sum+none));
  writeln('Площадь фигуры = ',S2:2:2);
end.

Программа полностью:  __VARD_1.PAS ( 1.61 килобайт ) Кол-во скачиваний: 400


Это уже будет работать быстрее алгоритма со случайными числами, т.к. "тяжелая" операция генерации чисел просто отсутствует, и заменена на гораздо более простую - перебор в цикле.

Но и это еще не предел... Как я уже писал выше, оптимизируем программу.
1) заменяем Real на Double
2) вместо того, чтобы в цикле выполнять Sqrt, можно ДО цикла возвести все mas[i] в квадрат, и потом сравнивать квадраты
3) целочисленные X := X + 1 заменяем на Inc(X). Вот что имеем:

  sum:=0; none := 0;
  tm_s:= MemL[$0040:$006c]; { контроль времени }

  for i := 1 to n do
    mas[i] := sqr(mas[i]);

  point_x := minx;
  while point_x <= maxx do begin

    point_y := miny;
    while point_y <= maxy do begin

      i := 1; found := False;
      While (i <= n) and not found do begin
        If (sqr(point_x-x[i])+sqr(point_y-y[i])) <= mas[i] then found:=true
        else inc(i);
      end;
      if found then inc(sum) else inc(none);

      point_y := point_y + delta;
    end;

    point_x := point_x + delta;
  end;

  tm_f:= MemL[$0040:$006c];
  tm_f:=tm_f - tm_s;

Программа полностью:  __VARD_2.PAS ( 1.66 килобайт ) Кол-во скачиваний: 436


Вторая программа выполняется быстрее первой почти в 25 раз !!!