Огненный Круг, Задача на Геометрию Опции

[Perfez]

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

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



Сообщение отредактировано: Perfez - 5.03.2007 20:45

[Чужак]

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

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./Задача о квадратуре круга
с пом.циркуля, кар. и линейки не решается/)

[Lapp]

Нужно пройтись по квадратам, проверяя, есть ли у них точки, находящиеся на расстоянии меньше 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 века - она занимала еще древних греков, насколько мне известно..

[Perfez]

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


вот сам pas файл:
 1490.pas ( 146 байт ) Кол-во скачиваний: 584


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

[Lapp]

посоветуй что-нибудь

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



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

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

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

[Perfez]

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



 1490.pas ( 176 байт ) Кол-во скачиваний: 555

[Lapp]

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

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

Сообщение отредактировано: Lapp - 28.02.2007 18:31

[volvo]

может ещё что-нибудь посоветуешь?

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

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;

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

[Perfez]

 
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,и бубен не катит... А жаль,мог бы легко отделаться...

[Perfez]

3. В х кладем R (координаты)

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

[Lapp]

3. В х кладем R (координаты)
- Обьясни пожалуйста,как понять?

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

[Perfez]

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

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

[volvo]

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

4. Делаем условный цикл: пока x^2+y^2>R^2 , уменьшаем х на 1 (если x<0 - выходим)
5. Увеличиваем z на x

заменил на

4. Устанавливаем X в [sqrt(R² - Y²)]
4а. Условный цикл: пока x²+y²<R² увеличиваем X на 1 ...
5. Увеличиваем z на x

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

[Lapp]

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

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

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 вне цикла - очень здравая идея

[Perfez]

z:=0;

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

[volvo]

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

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

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

[Perfez]

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

6. Увеличиваем y на 1

for y=R downto 0 begin

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

[Lapp]

Так,так...ну не понимаю я это алгоритм...
Ну нельзя же изменять значение у в цикле,разве я не прав?

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

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

[Lapp]

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


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

[Perfez]

Я наконец-таки понял алгоритм и смастерил-что-то вроде этого?  1490.pas ( 200 байт ) Кол-во скачиваний: 607
если да то он выводит неправильный результат...