Найти непересекающиеся окружности Опции

[Carrera]

Я вообще не понимаю в програмировании.Никогда не было информатики а тут надо одну задачу решить и зачет.Рещите пожалуйста кто умеет .Нужно в турбо паскале.Буду оч благодарна(шоколадку обеспечу))


Окружность на плоскости задана координатами X,Y,R-радиус(все значения формируются случайным образом).Из 20-ти окружностей показать те,которые не пересекают другие.

[Lapp]

Примерно вот так:

const
  n= 20;

var
  c: array[1..n] of record
    x,y,r: double
  end;
  i,j: integer;

begin
  randomize;
  for i:=1 to n do with c[i] do begin
    x:= random*100-50;
    y:= random*100-50;
    r:= random*12
  end;
  for i:=1 to n do with c[i] do begin
    write(i:3,':    x=',x:7:3,'  y=',y:7:3,'  r=',r:6:3);
    j:= 1;
    while (j<=n) and ((i=j) or (Sqrt(Sqr(c[j].x-x)+Sqr(c[j].y-y))>c[j].r+r)) do inc(j);
    if j>n then writeln('  - не пересекается с другими') else writeln
  end;
  readln
end.

[Carrera]

Спасибо огромное!!как тебе шоколадку передать?

[IUnknown]

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

Я про вот такой случай:

const
  n = 4;
  c: array[1..n] of record
    x,y,r: double
  end =
  (
    (x:3; y:3; r:1),
    (x:7; y:2; r:1),
    (x:8; y:5; r:1), // <-- Лежит внутри №4
    (x:8; y:5; r:3)
  );

[Lapp]

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

Да, я тоже так думаю. Спасибо, Володь, я опять выпустил этот случай из виду, +1 тебе.
Конечно, нужно проверять вложенные окружности.. Как-то вот так, если не ошибся в спешке:

const
  n= 20;

var
  c: array[1..n] of record
    x,y,r: double
  end;
  i,j: integer;

begin
  for i:=1 to n do with c[i] do begin
    x:= random*100-50;
    y:= random*100-50;
    r:= random*12
  end;
  for i:=1 to n do with c[i] do begin
    write(i:3,':    x=',x:7:3,'  y=',y:7:3,'  r=',r:6:3);
    j:= 1;
    while
      (j<=n) and (
        (i=j) or
        (Sqrt(Sqr(c[j].x-x)+Sqr(c[j].y-y)) > c[j].r+r) or    { лежит снаружи }
        (Sqrt(Sqr(c[j].x-x)+Sqr(c[j].y-y)) < abs(c[j].r-r))  { лежит внутри }
      )
    do inc(j);
    if j>n then writeln('  - не пересекается с другими') else writeln
  end;
  readln
end.

Спасибо огромное!!как тебе шоколадку передать?

Спасибо!
Боюсь, передача выйдет тебе недешево: полшоколадки на один континент, пол - на другой.. )) Мы с IUnknown дарим ее тебе (верно, Володь?), съешь сама. Только честно!

[Carrera]

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

[TarasBer]

> j:= 1;
> while (j<=n) and ((i=j) or (Sqrt(Sqr(c[j].x-x)+Sqr(c[j].y-y))>c[j].r+r)) do inc(j);

Мне этот код почему-то напомнил вот это: http://govnokod.ru/4883
Там человек задался целью написать всю логику программы в одном булевом выражении в заголовке while.
Я надеюсь, ты это написал не всерьёз, а чтобы оставить человеку "на дом" задачу переделать это в нормальный вид.


Ну и чисто от себя добавлю, что в данной задаче можно избавиться от квадрата (перебор всех пар окружностей), если ввести сетку и хеширование.
Я уж не говорю о том, что вместо sqrt(a)>b выгоднее проверять a>sqr(b).

Сообщение отредактировано: TarasBer - 19.10.2011 15:40

[Lapp]

Я надеюсь, ты это написал не всерьёз, а чтобы оставить человеку "на дом" задачу переделать это в нормальный вид.
Ну и чисто от себя добавлю, что в данной задаче можно избавиться от квадрата (перебор всех пар окружностей), если ввести сетку и хеширование.

Ну, ясно дело, тут есть, что оптимизировать.. ))

Я уж не говорю о том, что вместо sqrt(a)>b выгоднее проверять a>sqr(b).

Может быть, но я не уверен..

[TarasBer]

> но я не уверен..

В чём? Что умножить число на себя быстрее, чем взять корень? Или что b не окажется отрицательным? Или что переполнения с типом double тут не случится?