народ, помогите пож решить олимпиадную задачку

[mihandroz]

Дан шар радиуса R, центр которого находится в центре координат. определить количество точек с целочисленными координатами, находящихся на его поверхности.
(програма должна: запросить целое число R (0<R<=1000)-радиус шара. Подсчитать и сообщить число точек с целочисленными координатами, лежащих на поверхности шара.)
Пример 1: Если R=13, то К=78
Пример 2: если R=16, К=6
Примечание. Ограничение времени на прохождение одного теста - 20 секунд.

[eoln]

Идея такая, проводим сечения сферы параллельно оси Z, получаем 2R+1 окружность (R - целое), В каждой окружности проводим хорды параллельные оси Y, для каждой хорды вычисляем значение X. Проверяем если X - целое, то считаем точку (вернее 2 симметричных точки, исключая совпадающие).
Вот накидал пример. НО!!! Мы то люди если сложим 1/3 и 1/3 и 1/3 получим 1, а компьютер погрешность может дать маленькую. Вот и тут также. Даже если тип переменной менять (double или single), то всё равно есть погрешность.
Вобщем вот идея, а програмно доработать надобны будет

{$N+}
const
  e = 0.01;//та самая погрешность
var
  y, z, j, k, R: integer;
  newR, x: double;
begin
  write('R = ');
  readln(R);
  k := 0;
  for z := -R to R do
  begin
    newR := sqrt(sqr(R)-sqr(z));
    //newR - радиус окружностей при сечении
    j := trunc(sqrt(sqr(R)-sqr(z)));
    //строим хорды
    for y := -j to j do
    begin
      x := sqrt(sqr(newR) - sqr(y));
      if abs(frac(x)) < e then begin
        writeln(x:8:0, y:8, z:8);
        //один конец хорды
        inc(k);
        if x <> 0 then//если хорда не вырождается в точку
        begin
          writeln(-x:8:0, y:8, z:8);
          //другой конец хорды
          inc(k)
        end
      end
    end;
  end;
  writeln('Otvet = ', k);
  readln
end.

>>>Добавлено. Можно сразу почти в 8 раз ускорить работу, ведя расчёт для 1/8 сферы, но т.к. в задании ограничение на 20 секунд, можно не мучаться и оставить как есть - времени хватает с избытком

[Ламер_001]

хм.... а не слишком ли будет долго работать? чилса ведь не маленькие... хотя это решение "в лоб" и является верным... я думаю все же считать только в 1/8 шара (в силу симметрии) а потом значение *8.
а вот как бы от перебора избавится это надо думать

[eoln]

Ламер_001, а ты код скопируй и проверь что с максимально возможными данными (без вывода на экран - это я от себя добавил) время менее полсекунды!!! А про 1/8 я уже упомянул. Как Вы от перебора-то избавитесь? Не полезное у вас сообщение получается...

[Ламер_001]

ну раз укладывается, то Вы молодец, только вот при 13 ответ Ваш 70.
>>> добавлено ну а насчет упоминания я не заметил т.к. открыл окно чуть раньше

[puporev]

Мне кажется, решается проще и только в целых числах. На примере окружности это выглядит так. Радиус и его проекции на оси координат образуют прямоугольный треугольник. Координаты будут целыми, если целые числа a,b и R образуют зависимость a^2+b^=R^2, например всем известные тройки 3,4,5; 5,12,13; При R=5 точек с целыми кординатами будет 4 на осях (0,5;0,-5;5,0;-5,0) и 8 не на осях (3,4;4,3;-3,4;-4,3;-3,-4;-4,-3;3,-4;4,-3). Так же и со сферой, только там, если нет целых решений треугольника при данном R, то точек будет 6, если есть, то больше. Это просто идея такая, а воплощать ее тому, кто на олимпиаду собрался. Если и сейчас не решит, то и на олимпиаде делать нечего.
а нахождение количества ненулевых точек на плоскости простое
for i:=1 to R do
for j:=1 to R do
if i*i+j*j=R*R then ...
На сфере почти также.
Нулевые считать не надо, их на окружности всегда 4, на сфере - 6.

[puporev]

От увиденной сложности сам начал сложно думать, а решается то совсем просто. Они задачи списывают из учебников 1980-х годов, когда 20 сек было круто и с толку сбивают. Вот решение:

uses crt;
var x,y,z,R,K:integer;
begin
clrscr;
write('R=');readln(R);
K:=0;
for x:=-R to  R do
for y:=-13 to R do
for Z:=-13 to R do
if x*x+y*y+z*z=R*R then
inc(K);
writeln('K=',K);
readln
end.

[Serge_Bliznykov]

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

for x:=-R to  R do
for y:=-13 to R do
for Z:=-13 to R do

а при чём здесь -13 ??
Вы хотели сказать

for x:=-R to  R do
for y:=-R to R do
for Z:=-R to R do

?
И, у меня при R=1000 считалось заметно более 20 секунд... :-(

[Somebody]

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

И, у меня при R=1000 считалось заметно более 20 секунд... :-(

У меня для 500 считается чуть меньше 20 секунд. Значит, если считать для 1/8 сферы на 1000, будет тоже около 20.

[alexBlack]

Думаю решение в лоб не пройдет. Нужна оптимизация (это все-таки олимпиадная задача). Но по сегодняшним меркам 20 сек. это много.

Чтобы было интересней переформулируем.

Определить число точек с целочисленными координатами, лежащих на поверхности шара радиуса R для всех целых R в диапазоне [0 .. 1000] за время менее 10 сек.

т.е. получить последовательность:
1 6 6 30 6 30 30 54 6 102 30 78 30 78 54 150 6 102 102 126 30 270 78 150 30 150 78 318 54 174 150 198 6....

Несложная оптимизация позволяет найти все решения за 5 сек. Есть даже вариант, который считает за 3 сек.

Подсказка для ТС. Во-первых сферу можно делить не на 8, а на 16, а во-вторых перебирать не все множество (x, y), а только точки на ломаной, лежащей вблизи окружности.