Важно:Сразу прошу вас не пишите готовую программу ,а только объясните сам алгоритм в кратце:
Это задача с онлайн :http://acm.timus.ru/problem.aspx?space=1&num=1490
Лич Сандро проводит свои научные исследования в магии огня. Сандро стоит в центре огромного квадратного зала площадью 1000000 квадратных километров, сплошь замощённого квадратными каменными плитами со стороной один метр. По взмаху посоха вокруг Сандро возникает огненный круг радиуса R метров. Центр круга совпадает с центром зала и находится в месте соприкосновения 4-х плит. Сандро хочет посчитать, сколько плит будет испорчено огнем. Считается, что плита испорчена, если она имеет хотя бы две общие точки с кругом. На рисунке в качестве примера изображены плиты, испорченные огненным кругом радиуса 4:

Исходные данные
В единственной строке записано целое число R > 0 — радиус огненного круга. R не превосходит 10^5.
Результат
Выведите целое число — количество испорченных плит.
Примеры:
2-16
4-60

Ну, промежуточное /графическое/ решение может выглять
примерно так...

program Setka;
  uses graph;
  const r=155;
  var Gd, Gm, i: Integer;
  begin
    Gd := Detect; i:=0;
    InitGraph(Gd, Gm, ' ');
    setcolor(15);
    while i<600 do
    begin
    i:=i+40;
    Line(0+i,0,0+i,500); Line(0,0+i,920,0+i);
    circle(320,240,r);
    end;
    OutTextXY(325, 245, '0,0');
    OutTextXY(365, 245, '1'); OutTextXY(325, 205, '1');
    readln;
  end.

Затем пальцем по экрану-считать /шутка /
Сделать то же, но не графически, а через формулы площадей...
(Кстати, напоминает задачу геометров 16в/кажется/ о квадратуре круга-
как построить круг,с помощью циркуля,карандаша и линейки,
по площади равный данному квадрату со стороной N./Задача о квадратуре круга
с пом.циркуля, кар. и линейки не решается/)

Нужно пройтись по квадратам, проверяя, есть ли у них точки, находящиеся на расстоянии меньше R от центра. При этом можно учесть следующее..

Во-первых, достаточно пройтись по одному квадранту - например, x>0, y>0 - а потом домножить результат на 4.
По-хорошему, нужно было и квдрант поделить биссектрисой пополам, но это немного усложнит алгоритм (поскольку пришлось бы отдельно учитывать квадраты, лежащие на биссектрисе)..
Во-вторых, достаточно ограничится проверкой квадратов, которые лежат на расстоянии не более R от центра по каждой координате.
В третьих, достаточно проверять только одну точку каждого квадрата - а именно, левый нижний угол (если квадрант выбран, как сказано выше).

Таким образом, получаем двойной цикл (по x и по y) от 0 до R. Расстояние вычисляем по теореме Пифагора. Соотношение для проверки получается следующее:

Sqrt(x^2+y^2)<R

Но, учитывая, что квадратный корень может дать некоторую ошибку, я бы предпочел проверять сами квадраты:

x*x + y*y < R*R

Если это условие выполнено - круг испорчен, если нет - замена плитки не требуется..
Обрати внимание на строгое неравенство в условии! При нестрогом выполнении, может произойти "касание" в одной точке, что (по условию гарантии ) не является большим повреждением..
Не забудь полученное число умножить на 4 (либо првести циклы от -R до R)

2 Чужак:
Эта задача не имеет никакого отношения к квадратуре круга. Кстати, КК гораздо древнее XVI века - она занимала еще древних греков, насколько мне известно..

огромное спасибо,Lapp. но существует одна проблема взгляни на screen:
Нажмите для просмотра прикрепленного файла

вот сам pas файл:
Нажмите для просмотра прикрепленного файла

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

Я же сказал: используй вторую форму! с квадратами.. Она должна работать быстрее. При этом вычисли R^2 заранее.



Добавлено через 1 мин.
Кроме того, не вижу у тебя обнуления z перед циклом.

Добавлено через 2 мин.
То есть с перемножениями, извини. Хотя, скорее всего это все равно..

Но вынос R*R за оба цикла должен сработать. А вычисление x*x можно вынести за внутренний цикл, во внешний.

может ещё что-нибудь посоветуешь? ...если не надоел я ещё
Нажмите для просмотра прикрепленного файла


Нажмите для просмотра прикрепленного файла

Сходил по ссылке, глянул. Ситуация серьезная..
Нужно менять алгоритм полностью.
Например, так..

1. Обнуляем z (счетчик плиток).
2. Обнуляем y
3. В х кладем R (координаты)
4. Делаем условный цикл: пока x^2+y^2>R^2 , уменьшаем х на 1 (если x<0 - выходим)
5. Увеличиваем z на x
6. Увеличиваем y на 1
7. Если y>R - выходим.
8. Переходим к 5

Это будет обход по контуру круга, начиная справа-снизу квадранта (четверти круга). Плитку суммируем горизонтальными полосами. Заметь, что у снова можно возводить в квадрат вне цикла.

Через минут 10-15..
Исправляю два пункта: 4 и 7

А можно мне?
Смотри, что ты делаешь:

For x:=0 to r do
Begin

  t:=Sqr(x);
  For y:=0 to r do
  If t+Sqr(y)<q then Inc(z);

End;

Берем бубен, и ...

For x:=0 to r do
Begin

  t:=Sqr(x);
  For y:=0 to r do
  If t+Sqr(y)<q then Inc(z)
  Else Break; { <--- Все равно дальше - бесполезная работа }

End;

... а время выполнения - экономит...

 
var
x,y,r:longint;
z,q,t:longint;
Begin
ReadLn®;
q:=Sqr®;
For x:=0 to r do
Begin
  t:=Sqr(x);
  For y:=0 to r do
  If t+Sqr(y)<q then Inc(z)
  Else Break;
End;
z:=z*4;
WriteLn(z);
End.

Не Volvo,и бубен не катит... А жаль,мог бы легко отделаться...
Нажмите для просмотра прикрепленного файла

Обьясни пожалуйста,как понять?

Очень просто:
x:=R
Слово в скобках означает, что нововведенные переменные y и x - это координаты (типа пояснение)

Все эти 8 пунктов в цикле или я не понимаю обнуление на что?

Perfez, что-то там очень странное с тестами... Я пробовал делать так:

заменил на
Далее по алгоритму Lapp-а, программа летает, только проходит 9 тестов как положено, на 10-м выдает неправильный результат, хотя должно работать... Ничего не понимаю...

Это полный алгоритм. Обнуление - это значит "присвоить ноль".
Пишу фрагмент программы (примерно)

z:=0;
x:=R;
R2:=R*R;
for y=R downto 0 begin
  y2:=y*y;
  while (x*x+y2<R2)and(x>0) do Dec(x);
  Inc(z,x);
....

По ходу обнаружил ошибку - в п.8 переход не на 5, а на 4. Трудно уследить за нумерацией в такой записи.. Надеюсь, ты отслеживаешь смысл .


Добавлено через 4 мин.
Выитание R^2-y^2 вне цикла - очень здравая идея

Разве в Паскале,z автоматически не обнуляется?(Free Pascal)

Я бы не стал на это надеяться... Лучше сделать самому, чем потом искать ошибку, которой нет...

Кстати, то, что я написал выше я поправил - проблема была только в том, что по умолчанию Sqrt работает с Double, а мне надо было Extended... Доп. переменная решила проблему - все тесты пройдены...

Так,так...ну не понимаю я это алгоритм...


Ну нельзя же изменять значение у в цикле,разве я не прав?

Нельзя, верно. Но и не надо!
Я просто перенес изменение у в сам цикл.

Погоди, сейчас я нарисую картинку. Тогда поймешь..
Заходи минут через 15

Как обычно - снова обнаружил у себя ошибку.. Алгоритм правильный, ошибка в фрагменте кода. Почему-то я цикл по y перевернул - странно.. Цикл должен быть от 0 до R, конечно.


Вот, смотри, наглядно на рисунке.
Начинаем справа внизу.
Красные стрелки - цикл по y, зеленые - внутренний цикл с уменьшением x.
Желтые клетки - те на которых останавливается внутренний цикл.
Голубые - те, которые он проходит.
Суммируем те клетки, что слева от желтых (включая их тоже).

Нажмите для просмотра прикрепленного файла

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

Насколько неправильный? Пока я замечаю только, что строое неравентво в условии while нужно заменить на нестрогое... Это может дать некоторое количество лишних плиток..
Позже гляну поточнее и попробую (если проблема останется).

при 4 он выводит 80,хотя он должен выводить 60...
ни этот вариант:

While (Sqr(x)+Sqr(y)>q) and (x<0) do

ни этот вариант:

While (Sqr(x)+Sqr(y)>=q) and (x<=0) do

ни этот вариант:

While (Sqr(x)+Sqr(y)>q) and (x<=0) do

и ни этот вариант:

While (Sqr(x)+Sqr(y)>=q) and (x<0) do

не катят...

Вот этот должен прокатить

  While (Sqr(x)+Sqr(y)>=q) and (x>=0) do Dec(x);
  Inc(z,x+1);

Попробуй, а я пока разберусь с разными версиями..

While (Sqr(x)+Sqr(y)>q) and not (x<0) do

я нашёл свою ошибку,хотя она ничего не меняет... на этот раз при 4 он выводит 48...

Да, делай как я написал в предыдущем сообщении. Надо было просто аккуратно разобраться с номерами квадратов и координатами углов (у N-ного квадрата мы проверяем левый нижний угол, то есть с координатой N-1 по х).
Так что в этой версии все, вроде, должно быть правильно.
Можно подойти и по-другому (номер квадрата считать по левому углу, то есть начинать с нулевого), но смысл тот же..
Тяжело с такими тонкостями разбираться "устно", без программы..

И вынеси же возведение у в квадрат и вычитание за пределы внутреннего цикла!

p:=q-Sqr(y);
While (Sqr(x)>=p) and (x>=0) do Dec(x);
Inc(z,x+1);

PS
Обрати внимание на знак второго неравенства - оно у тебя был перевернуто..

ню-ню... все равно,хоть и на десятом тесте не проходит:
Нажмите для просмотра прикрепленного файла

Добавлено через 2 мин.
Нажмите для просмотра прикрепленного файла

Добавлено через 2 мин.

=

Это, кажется, уже проходили:

Смотри (выше), что сделал volvo для исправления этой ошибки..

Получаешь переполнение... Замени

y,x,r:longint;

на

y,x,r:Int64;

, и все будет в порядке...

Я засабмитил туда этот вариант (с longint) - и все прошло...

1551178 15:22:04 1 Mar 2007 Lapp 1490 Pascal Accepted 0.015 112 KB


Добавлено через 5 мин.
Вот код - скрываю спойлером, согласно просьбе автора темы

Очень, кстати, странно... Смотри:
То есть, вызывается версия , получающая и возвращающая LongInt... Смотрим дальше:

, из чего следует, что при R > 46340 результат в LongInt не поместится... Сбой налицо... Возможно, тебе просто повезло, и значения больше приведенного мной не передавались для теста твоей программе...

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

Действительно странно.. По условию - размер зала миллион на миллион метров..

Но я не думаю, что там случайным образом выбираются тесты. Кроме того, я прогнал еще раз - снова Ок.

Похоже на ошибку. Надо бы глянуть на условия на этом сайте.. Есть там что-то по синтаксису и т.п.?

в чём различия? я сойду с ума...

var
y,x,r:longint;
q,z,p:int64;
Begin
ReadLn®;
z:=0;
y:=0;
x:=r;
q:=Sqr®;
Repeat
p:=q-Sqr(y);
While (Sqr(x)>=p) and (x>=0) do Dec(x);
Inc(z,x+1);
y:=y+1;
Until y>r;
z:=z*4;
WriteLn(z);
End.

Добавлено через 16 мин.
вот абсолютно правильный вариант: Нажмите для просмотра прикрепленного файла
Нажмите для просмотра прикрепленного файла
спасибо огромное volvo и Lapp ,но я до сих пор не понимаю в чём различие моего и Lapp-овского вариантов... это невозможно объяснить...