Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2007.04.15;
Скачать: CL | DM;

Вниз

Олимпиадная задачка...   Найти похожие ветки 

 
infom ©   (2007-03-20 17:25) [0]

Сейчас сижу решаю одну олимпиадную задачу по программированию:

На листочке нарисована сетка со стороной квадратиков в H. Какое максимальное количество целых квадратиков может поместиться внутри окружности с данным радиусом R.

Интересны выши мнения... Есть ли у этой задачи абсолютное решение, т.е. функция F(H, R) возвращающее количество квадратиков ?

Я его не нашел


 
Vlad Oshin ©   (2007-03-20 17:34) [1]


> Есть ли у этой задачи абсолютное решение, т.е. функция F(H,
>  R) возвращающее количество квадратиков ?

есть


> Я его не нашел

я тоже :)
но оно есть, т.к. функция ограничена сверху площадью окружности


 
Ega23 ©   (2007-03-20 17:37) [2]

Смотри в сторону диагонали квадрата.


 
Ketmar ©   (2007-03-20 17:39) [3]

если ты начальник -- то решается элементарно. если подчинённый... не будем о грустном.


 
infom ©   (2007-03-20 17:41) [4]

> [1] Vlad Oshin ©   (20.03.07 17:34)

А мыслей нет куда копать ?

> [2] Ega23 ©   (20.03.07 17:37)

Смотрю.... ничего не вижу кроме его диагонали :) (Шучу, мысль понятна)

> [3] Ketmar ©   (20.03.07 17:39)

Тут уж луше я сам...


 
Ega23 ©   (2007-03-20 17:42) [5]

Стоп. А центр окружности где? В произвольном месте, на ребере или на узле?


 
Ega23 ©   (2007-03-20 17:45) [6]

Если в узле - то достаточно просто. смотришь, сколько целых диагоналей в радиус поместится - ну а дальше всё просто.


 
infom ©   (2007-03-20 17:50) [7]

> [6] Ega23 ©   (20.03.07 17:45)

В том то и сложность, что в задаче про центр ни слова, отсюда вывод.... центр может быть где угодно...


 
Ega23 ©   (2007-03-20 17:52) [8]


> В том то и сложность, что в задаче про центр ни слова, отсюда
> вывод.... центр может быть где угодно...


гм.. Это уже интересней. Но всё равно надо в сторону диагонали смотреть. ИМХО.


 
stud ©   (2007-03-20 18:00) [9]

Ega23 ©   (20.03.07 17:45) [6]
Если в узле - то достаточно просто. смотришь, сколько целых диагоналей в радиус поместится - ну а дальше всё просто.

а не проще ли найти максимально возможный квадрат, который можно вписать в окружность. и соответсвенно потом найти сколько квадратов с заданной стороной в него влезет.
вопрос вроде звучит
infom ©   (20.03.07 17:25)
Какое максимальное количество целых квадратиков может поместиться внутри окружности с данным радиусом R.

так какая разница где окажется центр окружности


 
VirEx ©   (2007-03-20 18:04) [10]

найди площадь окружности, найди площадь одного квадрата - вычисляй)


 
McSimm_   (2007-03-20 18:05) [11]

диаметр разделить на длину диагонали целочисленно и возвести в квадрат...


 
Ega23 ©   (2007-03-20 18:06) [12]


> а не проще ли найти максимально возможный квадрат, который
> можно вписать в окружность. и соответсвенно потом найти
> сколько квадратов с заданной стороной в него влезет.


Не-а. Представь, что размер стороны квадрата в сетке в тыщщу раз меньше стороны вписанного квадрата.


 
Sam Stone ©   (2007-03-20 18:08) [13]

а может сюда задачу о ранце припаять?


 
infom ©   (2007-03-20 18:08) [14]

> [9] stud ©   (20.03.07 18:00)


> [10] VirEx ©   (20.03.07 18:04)


> [11] McSimm_   (20.03.07 18:05)

Просто так решения с потолка предлагать не пойдет...правильных ниодного...


 
stud ©   (2007-03-20 18:11) [15]

Ega23 ©   (20.03.07 18:06) [12]
Не-а. Представь, что размер стороны квадрата в сетке в тыщщу раз меньше стороны вписанного квадрата.

и что???
как вариант sqr(sqrt(r^2) div h)


 
McSimm_   (2007-03-20 18:11) [16]


> > [11] McSimm_   (20.03.07 18:05)
>
> Просто так решения с потолка предлагать не пойдет...правильных
> ниодного...

Как отличить решение "с потолка" от правильного?


 
stud ©   (2007-03-20 18:12) [17]

хотя да, мелочевка не влезет


 
VirEx ©   (2007-03-20 18:14) [18]

причем здесь решение с потолка? я конечно не математик, но вроде так будет самое то:
целое число от(площадь окружности/площадь квадрата)


 
Ega23 ©   (2007-03-20 18:14) [19]


> хотя да, мелочевка не влезет
>


Вот именно.


 
McSimm_   (2007-03-20 18:17) [20]


> VirEx ©   (20.03.07 18:14) [18]

нет, у круга остаются участки в которые нельзя разместить ни одного квадратика, но их суммарная площадь может оказаться больше площади квадратика


 
infom ©   (2007-03-20 18:17) [21]

> [16] McSimm_   (20.03.07 18:11)

Достаточно протестировать на следующих данных
Пример1:
R = 2
H = 1
Ответ = 6

Пример2:
R = 3
H = 1
Ответ = 21


 
VirEx ©   (2007-03-20 18:20) [22]


>  [20] McSimm_   (20.03.07 18:17)

но ведь в ТЗ это и сказано:

> Какое максимальное количество целых квадратиков может поместиться
> внутри окружности

а "остаточная" или "суммарная" площадь здесь будут циферки после запятой которые и отбрасываются, мы ж всетаки количество квадратиков а не площадь вычисляем :)


 
infom ©   (2007-03-20 18:25) [23]

> [22] VirEx ©   (20.03.07 18:20)

Пример2: по вашему получается Пи*9 = 28 с лишним, а ответ 21 ...


 
VirEx ©   (2007-03-20 18:25) [24]

а, всё, дошло :(


 
McSimm_   (2007-03-20 18:28) [25]


> а "остаточная" или "суммарная" площадь здесь будут циферки
> после запятой которые и отбрасываются

нет, остаточная площадь может оказаться больше площади квадратика и не отбросится, хотя разместить целый квадратик и нельзя, мы его получим в ответе.


 
infom ©   (2007-03-20 18:30) [26]

> [21] infom ©   (20.03.07 18:17)

Простите
Пример1:
R = 2
H = 1
Ответ = 7


 
Sam Stone ©   (2007-03-20 18:32) [27]

Максимум по диаметру уместится окрвниз(диаметр/сторона_квадрата). Далее ищем 2 точки на окружности, проводим хорду, параллельную диаметру, на нее лепим еще квадратики. Все это математически выразить и получится то что надо :) Наверно)


 
McSimm_   (2007-03-20 18:32) [28]


> infom ©

я не учел участки вне вписанного квадрата


 
McSimm_   (2007-03-20 18:33) [29]


> на нее лепим еще квадратики.

просто так лепить нельзя, т.к. квадратики представляют из себя сетку, при произвольном размещении их можно вписать больше


 
VirEx ©   (2007-03-20 18:34) [30]

а если найти площадь одной доли квадрата, т.е. например разделить окружность на четыре дольки, и взять верхний правый кусок? а результат на 4 умножить


 
Sam Stone ©   (2007-03-20 18:35) [31]

> [29] McSimm_   (20.03.07 18:33)

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


 
VirEx ©   (2007-03-20 18:36) [32]

верятность превышения остаточной суммы площади уменьшится

хм. а если делить площадь на n=корень(r) частей?


 
McSimm_   (2007-03-20 18:47) [33]

"поставить" первую точку на окружность на 45 градусов, и запустить рекурсивный обход точек с шагом H от "первой" по всем "соседним" на предмет проверки лежит ли в пределах окружности, не считать точки, у которых отстутствуют соседи внизу и слева. Получится количество квадратиков.

:)


 
Циркуль   (2007-03-20 18:56) [34]

Осталось "45" обосновать :)


 
McSimm_   (2007-03-20 18:59) [35]

да, осталось доказать, что при расположении угла сетки на 45 градусах окружности количество квадратиков максимально.

доказать не могу.


 
Vlad Oshin ©   (2007-03-20 19:00) [36]


> > [1] Vlad Oshin ©   (20.03.07 17:34)
>
> А мыслей нет куда копать ?

читать надо про квадратуру круга, гиппократовы луночки
мне лень что-то, сегодня стока раз переписывал 30 строчечек - ни к какому умственному труду больше не способен :)


 
Sam Stone ©   (2007-03-20 19:10) [37]

> доказать не могу.

Вах! Мамой клянусь, да! :о)


 
Alexis ©   (2007-03-20 20:02) [38]

Через производные(или интегралы) тут как то надо, ИМХО ...


 
MBo ©   (2007-03-20 22:15) [39]

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

Берем один квадратик, описываем окружность мин. радиуса.
Добавляем второй, -//-
Добавляем третий таким образом, чтобы описанная окружность имела мин. радиус и т.д.

При значительном количестве квадратов очередной добавляется так, чтобы он был поближе к центру масс, а далекие не рассматривать, чтобы уменьшить количество вариантов (например, если есть 3x3, то сначала в центры сторон можно добавлять, а к углам - позже)

Кроме того, для ускорения нечто вроде антибинарного поиска можно соорудить - понятно, что зависимость R-N квадратичная, вот и делать округлые наборы из 1-4-9-16 и т.д. квадратов, и при нахождении примерного радиуса уже точнее подбирать.

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


 
TUser ©   (2007-03-20 22:56) [40]

Не так давно я кубики аналогично складывал. Задача у меня была - сколько кубиков на расстоянии не более чем константа от точки (хотя бы одна точка). Ну, центр тоже где-то в кубике. Тут тоже самое, только надо найти все квадратики, для которых все точки внутри коружности. Найти наибольшее расстояние легко. Следоватльеон, завел массив "инкрементов" + столько-то по осям от данного квадратика, отсортировал его + потом проверка тех квадратов, которые на границе. .... нифига никто не поймет



Страницы: 1 2 вся ветка

Текущий архив: 2007.04.15;
Скачать: CL | DM;

Наверх




Память: 0.57 MB
Время: 0.031 c
15-1174297229
WG
2007-03-19 12:40
2007.04.15
После переустановки офиса глючит OLE


2-1175132494
Wood
2007-03-29 05:41
2007.04.15
Позиция курсора в строке.


2-1173974506
Washington
2007-03-15 19:01
2007.04.15
Оформление


15-1173879490
Vlad Oshin
2007-03-14 16:38
2007.04.15
Проблема с копированием текста из delphi. крякозябы


5-1151657849
Chuk
2006-06-30 12:57
2007.04.15
Доступ к свойствам класса на основе Interface в RTTI