Олимпиадная задачка...

← →
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 операций произвести

> infom © (22.03.07 11:54) [55]

Ну да. Всегда интересно, когда временные рамки озвучивают и не говорят об остальном.
Вот в беларуси - 0,5 сек,- круто, а у нас 3 сек. А что одни на крее, а другие на БК-0010 - дело пятое.

> [56] Думкин © (22.03.07 12:05)

Я б даже сказал десятое, конфигурация сервера на котором компилятся и выполняются исходники мне не известна, но факт в том что задача легко решается алгоритмом за 1 секуду если R/h < 100

Конфигурация обычная... Не менее 2800 MHZ 512 RAM... Именно на такой и компилировали.

> Belorus © (22.03.07 16:10) [58]
Стесняюсь спросить... (С) Староконь

Это где на таких "обычных" компьютерах тестируют? Я как-никак в олимпиадах белорусских участвую, но не слышал чтобы больше 1700 МГц использовали. На сборах перед репой (Республиканской олимпиадой) тоже по субъективным ощущениям максимум 2 ГГц. И ОЗУ не больше 256 Мб.

> Именно на такой и компилировали
Хотя, если речь идёт только о компиляции, то, возможно, именно компиляция где-нибудь на таких компьютерах и проводится. А тестирование - уж извините...

Димоныч я не знаю в какой деревне ты живёшь. Но оба этапа областной олимпиады по Могилёвской области 2007 прошли именно на такой конфигурации..

Тесты прогонялись именно на том же компьютере где и компилировались.
Если в твоём колхозе Checker не используют , то пардон. Он как известно перед тестом компилирует.

На сборах у нас были опять же машины Celeron"ы на 2500. Что будет на республике - увидим.

> Belorus © (22.03.07 16:22) [60]
Деревня называется "Минская область". Впрочем, возможно субъективные ощущения подвели из-за ОС (2000)...

> но факт в том что задача легко решается алгоритмом за 1
> секуду если R/h < 100

Это понятно. Но не на МК-61 все-таки. Неужели неясно?

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