Версия для печати темы

Автор: Perfez 24.02.2007 22:55

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

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




Эскизы прикрепленных изображений

Автор: Чужак 28.02.2007 6:34

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

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.

Автор: Lapp 28.02.2007 7:15

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

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


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


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

Автор: Lapp 28.02.2007 12:53

Цитата(Perfez @ 28.02.2007 8:09)

Автор: Perfez 28.02.2007 17:52

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



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

Автор: Lapp 28.02.2007 18:16

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

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

Автор: volvo 28.02.2007 19:39

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 28.02.2007 20:15

 
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.

Автор: Perfez 28.02.2007 20:39

Цитата(Lapp @ 28.02.2007 15:16)

Автор: Lapp 1.03.2007 2:15

Цитата(Perfez @ 28.02.2007 16:39)

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

Автор: Perfez 1.03.2007 2:34

Цитата(Lapp @ 28.02.2007 15:16)

Автор: volvo 1.03.2007 3:10

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

Автор: Lapp 1.03.2007 3:18

Цитата(Perfez @ 28.02.2007 22:34)

Все эти 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);
....

Автор: Perfez 1.03.2007 3:30

Цитата(Lapp @ 1.03.2007 0:18)

z:=0;

Автор: volvo 1.03.2007 3:37

Автор: Perfez 1.03.2007 4:07

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

Автор: Lapp 1.03.2007 4:15

Цитата(Perfez @ 1.03.2007 0:07)

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

Автор: Lapp 1.03.2007 4:35

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


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

Автор: Perfez 1.03.2007 13:07

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

Автор: Lapp 1.03.2007 13:41

Цитата(Perfez @ 1.03.2007 9:07)

выводит неправильный результат...

Автор: Perfez 1.03.2007 16:14

при 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

Автор: Lapp 1.03.2007 16:21

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

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

Автор: Perfez 1.03.2007 16:25

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

Автор: Lapp 1.03.2007 16:40

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

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

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

Автор: Perfez 1.03.2007 16:55

ню-ню... все равно,хоть и на десятом тесте не проходит:


Добавлено через 2 мин.
 1490.pas ( 212 байт ) Кол-во скачиваний: 466


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

Цитата(Perfez @ 1.03.2007 13:25)

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

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

Автор: Lapp 1.03.2007 17:08

Цитата(Perfez @ 1.03.2007 12:55)

все равно,хоть и на десятом тесте не проходит:

Цитата(volvo @ 28.02.2007 23:10)

Автор: volvo 1.03.2007 17:12

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

y,x,r:longint;

y,x,r:Int64;

Автор: Lapp 1.03.2007 17:23

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

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


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

var
  y,x,r:longint;
  q,p,z: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.

Автор: volvo 1.03.2007 17:34

Автор: Lapp 1.03.2007 17:43

Цитата(volvo @ 1.03.2007 13:34)

Автор: Perfez 1.03.2007 18:40

Цитата(Lapp @ 1.03.2007 14:23)

var
  y,x,r:longint;
  q,p,z: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.

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.