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

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Огненный Круг

Автор: Perfez 24.02.2007 22:55

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

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

smile.gif


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

Автор: Чужак 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.


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

Автор: 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

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

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

Автор: Perfez 28.02.2007 12:09

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

вот сам pas файл:
Прикрепленный файл  1490.pas ( 146 байт ) Кол-во скачиваний: 380


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

Автор: Lapp 28.02.2007 12:53

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

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

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



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

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

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

Автор: Perfez 28.02.2007 17:52

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


Прикрепленный файл  1490.pas ( 176 байт ) Кол-во скачиваний: 341


Автор: Lapp 28.02.2007 18:16

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

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.


Не Volvo,и бубен не катит... no1.gif А жаль,мог бы легко отделаться... smile.gif
Прикрепленное изображение

Автор: Perfez 28.02.2007 20:39

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

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

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

Автор: Lapp 1.03.2007 2:15

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

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

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

Автор: Perfez 1.03.2007 2:34

Цитата(Lapp @ 28.02.2007 15: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

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

Автор: volvo 1.03.2007 3:10

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

Цитата(Lapp)
4. Делаем условный цикл: пока x^2+y^2>R^2 , уменьшаем х на 1 (если x<0 - выходим)
5. Увеличиваем z на x
заменил на
Цитата
4. Устанавливаем X в [sqrt(R2 - Y2)]
4а. Условный цикл: пока x2+y2<R2 увеличиваем X на 1 ...
5. Увеличиваем z на x
Далее по алгоритму Lapp-а, программа летает, только проходит 9 тестов как положено, на 10-м выдает неправильный результат, хотя должно работать... Ничего не понимаю...

Автор: Lapp 1.03.2007 3:18

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

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

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

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. Трудно уследить за нумерацией в такой записи.. Надеюсь, ты отслеживаешь смысл smile.gif.


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

Автор: Perfez 1.03.2007 3:30

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

z:=0;


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


Автор: volvo 1.03.2007 3:37

Цитата
Разве в Паскале,z автоматически не обнуляется?
Я бы не стал на это надеяться... Лучше сделать самому, чем потом искать ошибку, которой нет...

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

Автор: Perfez 1.03.2007 4:07

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

Цитата

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

Цитата

for y=R downto 0 begin

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

Автор: Lapp 1.03.2007 4:15

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

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

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

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

Автор: Lapp 1.03.2007 4:35

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


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

Прикрепленное изображение

Автор: Perfez 1.03.2007 13:07

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

Автор: Lapp 1.03.2007 13:41

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

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

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

Автор: Perfez 1.03.2007 16:14

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


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


не катят... no1.gif

Автор: Lapp 1.03.2007 16:21

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

  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

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

Автор: Lapp 1.03.2007 16:40

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

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

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


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

Автор: Perfez 1.03.2007 16:55

ню-ню... no1.gif все равно,хоть и на десятом тесте не проходит: smile.gif blink.gif
Прикрепленное изображение

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


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

Цитата

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

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

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

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

Автор: Lapp 1.03.2007 17:08

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

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

Это, кажется, уже проходили:
Цитата(volvo @ 28.02.2007 23:10) *

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

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


Автор: 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 мин.
Вот код - скрываю спойлером, согласно просьбе автора темы

Спойлер (Показать/Скрыть)

Автор: volvo 1.03.2007 17:34

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

Очень, кстати, странно... Смотри:
Цитата(RTL.pdf)
29.9.479 sqr
Synopsis: Calculate the square of a value.
Declaration: function sqr(l: LongInt) : LongInt
function sqr(l: Int64) : Int64
function sqr(l: QWord) : QWord
function sqr(d: ValReal) : ValReal
Visibility: default
Description: Sqr returns the square of its argument X.
Errors: None.
То есть, вызывается версия , получающая и возвращающая LongInt... Смотрим дальше:

Цитата(REF.pdf)
Table 3.2: Predefined integer types
Type Range Size in bytes
Byte 0 .. 255 1
Shortint -128 .. 127 1
Smallint -32768 .. 32767 2
Word 0 .. 65535 2
Integer either smallint, longint or int64 size 2,4 or 8
Cardinal either word, longword or qword size 2,4 or 8
Longint -2147483648 .. 2147483647 4
Longword 0..4294967295 4
Int64 -9223372036854775808 .. 9223372036854775807 8
QWord 0 .. 18446744073709551615 8
, из чего следует, что при R > 46340 результат в LongInt не поместится... Сбой налицо... Возможно, тебе просто повезло, и значения больше приведенного мной не передавались для теста твоей программе...

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

Автор: Lapp 1.03.2007 17:43

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

Очень, кстати, странно... Смотри:
..
Возможно, .. значения больше приведенного мной не передавались для теста твоей программе...

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

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

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

Автор: Perfez 1.03.2007 18:40

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

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

1551178 15:22:04 1 Mar 2007 Lapp 1490 Pascal Accepted 0.015 112 KB
Добавлено через 5 мин.
Вот код - скрываю спойлером, согласно просьбе автора темы
Спойлер (Показать/Скрыть)


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

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 мин.
вот абсолютно правильный вариант: smile.gif Прикрепленное изображение
Прикрепленный файл  1490.pas ( 202 байт ) Кол-во скачиваний: 340

спасибо smile.gif огромное volvo good.gif и Lapp good.gif ,но я до сих пор не понимаю в чём различие моего и Lapp-овского вариантов... wacko.gif blink.gif это невозможно объяснить... no1.gif wacko.gif blink.gif