Форум: "Прочее";
Текущий архив: 2007.04.15;
Скачать: [xml.tar.bz2];
ВнизОлимпиадная задачка... Найти похожие ветки
← →
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]Не так давно я кубики аналогично складывал. Задача у меня была - сколько кубиков на расстоянии не более чем константа от точки (хотя бы одна точка). Ну, центр тоже где-то в кубике. Тут тоже самое, только надо найти все квадратики, для которых все точки внутри коружности. Найти наибольшее расстояние легко. Следоватльеон, завел массив "инкрементов" + столько-то по осям от данного квадратика, отсортировал его + потом проверка тех квадратов, которые на границе. .... нифига никто не поймет
← →
infom © (2007-03-21 12:36) [41]Задачу все таки решил, всем спасибо. Конечно формулы получить не получилось, поэтому просто алгоритмизировал перебор квадратиков вероятно попадающих в круг и пересчитал их количество, для различных положений центра круга в квадрате....
Если кому интересно могу рассказать подробнее
← →
MBo © (2007-03-21 12:49) [42]Общих формул, похоже, нет даже для количества точек целочисленной решетки, попадающих в круг радиуса R c подвижным центром.
Для фиксированного центра (0,0) есть ряд Гаусса 1 + 4R + Sum{i}(чего-то там от i,R)
← →
Vlad Oshin © (2007-03-21 12:51) [43]
> infom © (21.03.07 12:36) [41]
а.. логично...
а какова таблица зависимостей:
длинна стороны квадрата - радиус - количество
может, можно обратно прийти к к.л. формуле
← →
infom © (2007-03-21 15:13) [44]> [43] Vlad Oshin © (21.03.07 12:51)
Зависимость очень сложная, полностью построены решения для соотношения R к H от 1 до 10....
> [42] MBo © (21.03.07 12:49)
А где об этом почитать можно ?
← →
MBo © (2007-03-21 15:52) [45]http://mathworld.wolfram.com/CircleLatticePoints.html
http://mathworld.wolfram.com/GausssCircleProblem.html
http://www.research.att.com/~njas/sequences/?q=circle+square+lattice&sort=0&fmt=0&language=english&go=Search
← →
Jeer © (2007-03-21 15:56) [46]
> infom © (21.03.07 15:13) [44]
Раздел "Геометрия/Комбинаторная/Целочисленные решетки"
(теорема Минковского)
Могут быть доказаны:
- для любого n существует окружность, внутри которой лежит ровно n целочисленных точек;
-для любого n существует окружность, на которой лежит ровно n целочисленных точек;
-внутри выпуклой фигуры с площадью S и полупериметром p лежит n узлов решетки. Причем: n > S - p.
← →
PEAKTOP © (2007-03-21 16:11) [47]Я бы решал так:
Пусть дано: окружность с центром в точке (Xo;Yo) и радиуса R на поверхности, состоящей из квадратов с координатами левого верхнего угла (Xi; Yi)и стороной d. Центр окружности может лежать и внутри какого-нибудь квадрата.
Тогда необходимое условие принадлежности квадрата окружности, это принадлежность всех его вершин окружности. Математически уже наверное выразить не смогу, но на паскале
const
d :Extended = 10; // Сторона квадрата
function InCircle(const Xo, Yo, R, Xi, Yi :Extended):Boolean;
var
B1, B2, B3, B4 :Boolean;
InCircle :Boolean;
begin
B1 := (Abs(Xo-Xi) <= R) and (Abs(Yo-Yi) <= R);
B2 := (Abs(Xo-(Xi + d)) <= R) and (Abs(Yo-Yi) <= R);
B3 := (Abs(Xo-Xi) <= R) and (Abs(Yo-(Yi+d)) <= R);
B4 := (Abs(Xo-(Xi + d)) <= R) and (Abs(Yo-(Yi+d)) <= R);
Result := B1 and B2 and B3 and B4;
end;
← →
Jeer © (2007-03-21 16:38) [48]
> PEAKTOP © (21.03.07 16:11) [47]
Нет смысла изучать на предмет принадлежности все вершины.
Проще "создать" контур (периметр) совокупности квадратов, лежащих внутри окружности поисковыми методами.
При это сразу считается число квадратов.
← →
PEAKTOP © (2007-03-21 18:09) [49]
> Jeer © (21.03.07 16:38) [48]
Задачка-то - олимпиадная :))) следовательно, производительностью мы можем пренебречь :)))
← →
Belorus © (2007-03-21 22:11) [50]Ага.. Особенно если учесть что на белорусских олимпиадах дают по 0.5 секунды и 64 мб памяти на задачу.. Если превышение - сразу 0 баллов.
← →
antonn © (2007-03-21 23:52) [51]
> Тогда необходимое условие принадлежности квадрата окружности,
> это принадлежность всех его вершин окружности.
квадрат и окружность могут пересекаться так, что ни одной вершины не будет в окружности...
← →
antonn © (2007-03-21 23:53) [52]а, блин, требовалось кол-во целых квадратиков:) сорри:)
← →
infom © (2007-03-22 11:23) [53]> [50] Belorus © (21.03.07 22:11)
Эта олимпиада похожа, только дается 3 сек
← →
Думкин © (2007-03-22 11:26) [54]
> infom © (22.03.07 11:23) [53]
> > [50] Belorus © (21.03.07 22:11)
>
> Эта олимпиада похожа, только дается 3 сек
и БК-0010
← →
infom © (2007-03-22 11:54) [55]> [54] Думкин © (22.03.07 11:26)
Как раз 5-6 операций произвести
← →
Думкин © (2007-03-22 12:05) [56]
> infom © (22.03.07 11:54) [55]
Ну да. Всегда интересно, когда временные рамки озвучивают и не говорят об остальном.
Вот в беларуси - 0,5 сек,- круто, а у нас 3 сек. А что одни на крее, а другие на БК-0010 - дело пятое.
← →
infom © (2007-03-22 12:12) [57]> [56] Думкин © (22.03.07 12:05)
Я б даже сказал десятое, конфигурация сервера на котором компилятся и выполняются исходники мне не известна, но факт в том что задача легко решается алгоритмом за 1 секуду если R/h < 100
← →
Belorus © (2007-03-22 16:10) [58]Конфигурация обычная... Не менее 2800 MHZ 512 RAM... Именно на такой и компилировали.
← →
ProgRAMmer Dimonych © (2007-03-22 16:14) [59]> Belorus © (22.03.07 16:10) [58]
Стесняюсь спросить... (С) Староконь
Это где на таких "обычных" компьютерах тестируют? Я как-никак в олимпиадах белорусских участвую, но не слышал чтобы больше 1700 МГц использовали. На сборах перед репой (Республиканской олимпиадой) тоже по субъективным ощущениям максимум 2 ГГц. И ОЗУ не больше 256 Мб.
> Именно на такой и компилировали
Хотя, если речь идёт только о компиляции, то, возможно, именно компиляция где-нибудь на таких компьютерах и проводится. А тестирование - уж извините...
← →
Belorus © (2007-03-22 16:22) [60]Димоныч я не знаю в какой деревне ты живёшь. Но оба этапа областной олимпиады по Могилёвской области 2007 прошли именно на такой конфигурации..
Тесты прогонялись именно на том же компьютере где и компилировались.
Если в твоём колхозе Checker не используют , то пардон. Он как известно перед тестом компилирует.
На сборах у нас были опять же машины Celeron"ы на 2500. Что будет на республике - увидим.
← →
ProgRAMmer Dimonych © (2007-03-22 16:41) [61]> Belorus © (22.03.07 16:22) [60]
Деревня называется "Минская область". Впрочем, возможно субъективные ощущения подвели из-за ОС (2000)...
← →
Думкин © (2007-03-22 19:05) [62]> но факт в том что задача легко решается алгоритмом за 1
> секуду если R/h < 100
Это понятно. Но не на МК-61 все-таки. Неужели неясно?
Страницы: 1 2 вся ветка
Форум: "Прочее";
Текущий архив: 2007.04.15;
Скачать: [xml.tar.bz2];
Память: 0.61 MB
Время: 0.043 c