Сервер олимпиад

Zakhr · Добавлено: 11.04.2007 21:29:53

Какие есть предложения как её можно решить?

admin · Добавлено: 12.04.2007 12:08:55

В задании требовалось найти максимальное количество квадратиков, помещающееся в круг => центр круга не обязательно лежит в геометрическом центре сетки квадратиков. Делаем шаг для центра квадратиков = корень из точности, перебираем положение центра и это решение уже проходит. Схожее с авторским - решение infom.

Zakhr · Добавлено: 12.04.2007 17:39:48

Я понял, что для решения этой задачи надо вокруг окружности описать квадрат размеры которого равны 2*R x 2*R. Далее проводится дискретизация этого пространства на маленькие прямоугольники H x H, затем в нашей сетке пройзводится перебор каждой клетки. Каждая клетка это квадрат который характеризуется своими вершинами для того чтобы узнать принадлежит ли он окружности необходимо проверить эти четыре точки если они все принадлежат, то увеличеваем число квадратиков на единицу и переходим к следующему квадрату, иначе (т.е. хотя бы одна т. не принадлежит окружности) то переходим к следующему квадрату H x H, таким образом произведём перебор всех квадратов из 2*R x 2*R и подсчитаем число входящих в окружность.

admin · Добавлено: 12.04.2007 17:43:47

они не обязательно в прямоугольнике.
например был такой тест (№3).
когда радиус=2, сторона квадрата=1.

вместится 7 квадратиков!

Zakhr · Добавлено: 13.04.2007 22:33:12

Не понятно как получилось 7 по вышеуказанному алгоритму который я описал чуть выше получается только 4.

admin · Добавлено: 13.04.2007 22:52:51

Нарисуйте в слое одном фотошопа сетку (ширина=1), в другом - круг с радиусом 2. И подвигайте один слой относительно другого.

Увидите что решением будет фигура из квадратиков:

XX
XXX
XX

Сервер олимпиад

Ставропольский государственный университет

Server Off-Line

Форум