[___toha___]

Здравствуйте.. Мой знакомый ходил на олимпиаду по информатике, 8 класс. Там была задачка. Вообщем никто не решил, спросили меня, я, тоже как-то не додумался. Спрашивал у многих "математиков", но они тоже не знают. Вот уже давно меня мучает эта задача, все-таки как её решить.
Суть:
Есть поле, с размерами X и Y. На нем размещены вышки, радиус действия которых R. Вообщем, дано 3 числа. X Y R. Нужно определить, сколько нужно разместить таких вышек (минимально), чтобы на всем поле была хорошая связь.
Может кто знает? А то я даже с точки зрения математики не пойму, как это.. Должно быть, наверно, что-то легкое, раз 8 классс.
Пример:
Даны числа 24 18 6. А получить нужно число 12.
Может кто знает, как это решить. Буду благодарен. Хотя бы с точки зрения математики

[YVitaliy]

Может туплю. Если в вашем примере 6 - это радиус вышек, то если элементарно эти вышки "превратить" в квадраты со стороной

Код:

a=6*sqrt(2)

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

[___toha___]

Вот тоже думаю.. Я даже писал таблицу, что если 1 кв.м поля, нужно 5 вышек, радиусом 0,5 кв.м. Если 2 кв.м, то уже 8 вышек, с радиусом 0,5. и т.д. Но ни к чему хорошему это не привело..

[lmikle]

Ну, если считать область действия вышки квадратом, то да.
Если это все-таки круг и мы считаем, что зона приёма бинарна (либо есть, либо нет), то тогда решением будет кол-во вписанных в окружность квадратов равное площади поля.
Сторона квадрата, вписанного в окружность есть радиус этой окружности. Соответсвтенно, получаем уравнение:
X*Y = N*R^2
Для нашего примера:
24*18=N*6^2
N=(24*18)/(6*6)=4*3=12.
Сходится?

[poli-smen]

Сообщение от lmikle

Сторона квадрата, вписанного в окружность есть радиус этой окружности.

Диаметр окружности будет соответствовать диагонали вписанного квадрата. Если представить что диагональ квадрата это гипотенуза, то стороны этого квадрата будут катетами прямоугольного треугольника равными в соответствии с теоремой Пифагора := D / Sqrt(2)
где D - это диаметр окружности

Но у меня есть подозрение, что заполнение треугольниками будет более плотным чем квадратами.

[lmikle]

Сообщение от poli-smen

Диаметр окружности будет соответствовать диагонали вписанного квадрата. Если представить что диагональ квадрата это гипотенуза, то стороны этого квадрата будут катетами прямоугольного треугольника равными в соответствии с теоремой Пифагора := D / Sqrt(2)
где D - это диаметр окружности

Но у меня есть подозрение, что заполнение треугольниками будет более плотным чем квадратами.

Да, это что-то я ошибся, невнимательно на картинку посмотрел.
Тогда получается 6. Принцип тот же, только площадь вписанного квадрата = 2R^2, соответственно:
X*Y = N*R^2
Для нашего примера:
24*18=N*2*6^2
N=(24*18)/(2*6*6)=2*3=6.
Ну тут либо они тоже ошиблись (причем именно так же, как я), либо тут еще что-то "зарыто".

А кто сказал, что должно получиться именно 12???

[Bargest]

А кто сказал, что должно получиться именно 12???

Вот именно, кто? Даже если взять первое, что приходит в голову (вписанные в окружность квадраты), получается максимум 9 ((24 / (6*sqrt(2))) * (18 / (6*sqrt(2))) с округлением результата делений в большую сторону), но никак не 12.
И кстати, lmikle, думаю нельзя так просто делить площадь - мб не получится покрыть зону именно квадратами и придется добавлять еще точки.

[___toha___]

12 взялось из примера. Там вот задача, а внизу примеры. Я вот тут тоже думал. У меня общая формула получилась XY/2R^2. Под под второй пример подходит (их там два)
Этот 24 18 6 = 12
И этот еще 24 10 6 = 4
Не получается это потому что это площади. То есть если некая фигура занимает площадь 100 кв.м, то это может быть квадрат, со стороной 10. Но это может быть и, допустим, прямоугольник, со сторонами 5 и 20, или же 2 и 50. А у нас должен получиться именно квадрат. Например, если возьмем по клеткам, 1 кл. будет равна диаметру окр. Допустим у нас будет прямоугольник со сторонами 6 клеток и 2 с половиной клетки. По логике у нас займется 1 строка, то есть 6 квадратов. Вторая - еще 6, итого 12, и третья (хоть не полная, но вышки на нее ставить нужно) еще 6, итого 18. А по программе получается так. 1 и 2 строки как у нас - 12, а вот третья, которая в высоту пол клетки, будет не 6, а 3 (так как в 2 раза меньше) итого 3. Всего получается 15. Ага. Там 18, а тут 15. Нужно значит что-то не так делать.. Но, вроде, мы где-то близко

Может попробовать дополнить размеры поля до числа, которое без остатка делится на диаметр, а потом проделать эти же манипуляции?!

[Bargest]

Я уже предложил, как сделать квадратами - делить отдельно длину и ширину поля, округлять результат вверх, умножать. Если сторона квадрата - 4, а поле - 7x9, то по ширине нужно 7/4 = 1 + 3/4 квадрата (округляем до 2, т.к. нужно больше 1) и по высоте 9/4 = 2 + 1/4 квадрата (округляем до 3, т.к. больше 2х). Умножаем, получаем 6 точек всего.
Однако не факт, что это оптимальное покрытие.

[Aristarh Dark]

У меня для 24 18 6 получилось 9, а для 24 10 6 получилось 6. Это без оптимизации

[lmikle]

Гм. Пусть ДНА есть квадрат. При алгоритме вычисления по сторонам (округление вверх пропускаю, просто что бы не замусоривать выкладки):
N = (X\R)*(Y\R)
В первом примере получается 12, А вот во втором - 8.
Но это бред. Надо узнать точное условие задачи, а то как в том анекдоте про Шаляпина...