Круг на плоскости

[JuniorProger]

Сообщение от evg_m

Нет, все целые точки лежат на лучах с углами в целые градусы (0-360). а могут и не лежать

Согласен.
Посмотри пост #10. Stilet говорит, что счетчик цикла показывает количество точек с целыми координатами внутри окружности (ну как в задании).

[evg_m]

пост #6 от JuniorProger
совсем немного не дотянул до хорошего решения.

n:=0;
for y:=trunc(y0-r) to trunc(y0+r) do begin
  left_border:=trunc(x0-sqrt(sqr(r)-sqr(y-y0)));
  right_border:=trunc(x0+sqrt(sqr(r)-sqr(y-y0)));
  for x:=left_border to right_border do
    inc(n);
end;

смотрим последние две строчки
внутри цикла чисто +1 какое-то число раз.
заменяем цикл на

n:=n+(right,border -left.border);

получаем

for y:=trunc(y0-r) to trunc(y0+r) do 
  n:=n+(trunc(x0+sqrt(sqr(r)-sqr(y-y0))) -trunc(x0-sqrt(sqr(r)-sqr(y-y0))));

[JuniorProger]

Сообщение от evg_m

пост #6 от JuniorProger
совсем немного не дотянул до хорошего решения.

смотрим последние две строчки
внутри цикла чисто +1 какое-то число раз.
заменяем цикл на

n:=n+(right,border -left.border);

получаем

for y:=trunc(y0-r) to trunc(y0+r) do 
  n:=n+(trunc(x0+sqrt(sqr(r)-sqr(y-y0))) -trunc(x0-sqrt(sqr(r)-sqr(y-y0))));

Нужно прибавлять +1 иначе не будет учтена одна точка для каждого Y! Смотреть пост #6 нижнее решение

[TinMan]

Сообщение от JuniorProger

Функция trunc не зависит от знака! Сам проверял: она берет целую часть от модуля числа, потом добавляет знак, если был таковой. Поэтому не важно, какое число (положительное или отрицательное), trunc всегда возьмет только целую часть!

JuniorProger, просто подумай над тем, что ты сказал.
И еще раз прочти мой пост выше.
Уверен, ты поймешь ).

[JuniorProger]

Сообщение от TinMan

JuniorProger, просто подумай над тем, что ты сказал.
И еще раз прочти мой пост выше.
Уверен, ты поймешь ).

Я понял, что при отрицательном входном значении trunc вернет число большее либо равное входному (но меньшее или равное по модулю), а при положительном - меньшее или равное.
Под знакозависимой я (да и не только) понимаю функцию, результат работы которой зависит от знака аргумента. Но Trunc при любом входном значении (отрицательном или положительном) вернет целую часть. Вот, скажем, sqrt() - знакозависимая, т.к. при положительном аргументе она вернет корень, а при отрицательном - ошибку.

Ну да ладно, каждый пусть думает как хочет

[TinMan]

Сообщение от JuniorProger

Ну да ладно, каждый пусть думает как хочет

Не в этом дело. Дело в правильности результата программы. Я отметил, что если использовать trunc, то нужны поправки на знак. Если ты настроен спорить о терминах, то рассмотри график функции trunc и заметь, что при смене знака аргумента ход графика претерпевает некий "излом". Но на самом деле строгого термина такого нет, и все, что я хотел сказать этим словом - что нужно учитывать знак аргумента.

Выше я уже сказал, как с этим бороться. Могу повторить то же самое на Pascal.

  // сначала сдвигаем круг (если нужно) так, чтобы он был полностью в первом квадранте:
  d:= x0 - r;
  if d<0 then x0:= x0 + Trunc(-d) + 2;
  d:= y0 - r;
  if d<0 then y0:= y0 + Trunc(-d) + 2;
  // теперь можно считать точки с использованием trunc, не волнуясь о знаках
  // ...

Но есть лучшее решение этого вопроса. Более красивое, более общее, более простое и ясное, не перегруженное проверками. Не знаю, стоит ли приводить его после того, как задача решена..

[puporev]

Не знаю, стоит ли приводить его после того, как задача решена.

Конечно стоит, ибо я например не уверен что она решена для r=1000000.

[JUDAS]

function Ceil(const X: Extended): Integer;
begin
  Result := Integer(Trunc(X));
  if Frac(abs(X)) > 0 then
  case X>0 of
   true : Inc(Result);
   false: Dec(Result);
  end;
end;


function PointCountByCircle(Cx,Cy ,R : double) : integer;
var Rin,Rout : TRect;
    i,j,dx   : integer;
    D,insize : double;
begin
 // 1. ищем вписаный квадрат с окрулением координат углов к центру
 D := R*cos(pi/8);
 Rin.Left:= Trunc(Cx-D);  Rin.Right  := Trunc(Cx+D);
 Rin.Top := Trunc(Cy+D);  Rin.Bottom := Trunc(Cy-D);

 // 2. ищем описаный квадрат с округлением координат сторон от центра
 Rout.Left:= Ceil(Cx-R-1E-8);  Rout.Right  := Ceil(Cx+R+1E-8);
 Rout.Top := Ceil(Cy+R+1E-8);  Rout.Bottom := Ceil(Cy-R-1E-8);
 insize := Rin.Right-Rin.Left;
 result := 1;
 if insize<>0 then result := round(sqr(insize+1));

 for j:= Rout.Bottom to Rout.Top do
 begin
   for i:= Rout.Left to Rin.Left-1 do
   inc(result, byte(sqrt(sqr(i-Cx)+sqr(j-Cy))<=R));
   for i:= Rin.Right+1 to Rout.Right do
   inc(result, byte(sqrt(sqr(i-Cx)+sqr(j-Cy))<=R));
 end;

 if insize=0 then dx:=0 else dx:=1;

 for i:= Rin.Left+dx to Rin.Right-dx do
 begin
   for j:= Rout.Bottom to Rin.Bottom-1 do
   inc(result, byte(sqrt(sqr(i-Cx)+sqr(j-Cy))<=R));
   for j:= Rin.Top+1 to Rout.Top do
   inc(result, byte(sqrt(sqr(i-Cx)+sqr(j-Cy))<=R));
 end;

end;

такой код прокатит?
по крайней мере не "маслает" вписанный в круг квадрат, который и так внутри (проверяется желтая область)

радиус = 100000 считало минуты 2 с результатом - 1348027629 точек

[TinMan]

Сообщение от JUDAS

такой код прокатит?
по крайней мере не "маслает" вписанный в круг квадрат,

Боюсь, этого мало..

радиус = 100000 считало минуты 2 с результатом - 1348027629 точек

Во-первых, ты не сказал координаты центра круга. Во-вторых, результат явно неверный, поскольку приблизительно при r=10^5 он должен быть такой:
S = 3.1415925*10^10

Вот мой код, который для r=10^6 просчитал практически мгновенно (для 10^7 примерно секунду), при этом я даже не отключал отладочный режим. В этом коде вместо функции trunc используются две функции: Up и Down - которые выдают соответственно ближайшее большее и ближайшее меньшее целое. Эти функции очень полезно написать и иметь в своей библиотеке. Думаю, вас не затруднит это сделать..

uses MyLib;
var
  r,x,y,a: double;
  i: LongInt;
  n: comp;

begin
  readln(r,x,y);
  n:= 0;
  for i:= Up(x-r) to Down(x+r) do begin
    //writeln(x-i);
    a:= Sqrt(r*r-Sqr(x-i));
    n:= n + Down(y+a) - Up(y-a) + 1
  end;
  write(n);
  readln
end.

Результаты для сравнения такие:

Running "h:\...\circle.exe "
1000000 1.234 5.6789
3141592653367
Running "h:\...\circle.exe "
10000000 1.234 5.6789
314159265358851

[JUDAS]

координаты центра круга = 0,0
TinMan, а что собственно твой код считает ?