|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
|
Опции темы | Поиск в этой теме | Опции просмотра |
#1
|
||||
|
||||
Задача из старой олимпиады
Здравствуйте.. Мой знакомый ходил на олимпиаду по информатике, 8 класс. Там была задачка. Вообщем никто не решил, спросили меня, я, тоже как-то не додумался. Спрашивал у многих "математиков", но они тоже не знают. Вот уже давно меня мучает эта задача, все-таки как её решить.
Суть: Есть поле, с размерами X и Y. На нем размещены вышки, радиус действия которых R. Вообщем, дано 3 числа. X Y R. Нужно определить, сколько нужно разместить таких вышек (минимально), чтобы на всем поле была хорошая связь. Может кто знает? А то я даже с точки зрения математики не пойму, как это.. Должно быть, наверно, что-то легкое, раз 8 классс. Пример: Даны числа 24 18 6. А получить нужно число 12. Может кто знает, как это решить. Буду благодарен. Хотя бы с точки зрения математики |
#2
|
||||
|
||||
Может туплю. Если в вашем примере 6 - это радиус вышек, то если элементарно эти вышки "превратить" в квадраты со стороной
Код:
a=6*sqrt(2) |
#3
|
||||
|
||||
Вот тоже думаю.. Я даже писал таблицу, что если 1 кв.м поля, нужно 5 вышек, радиусом 0,5 кв.м. Если 2 кв.м, то уже 8 вышек, с радиусом 0,5. и т.д. Но ни к чему хорошему это не привело..
|
#4
|
|||
|
|||
Ну, если считать область действия вышки квадратом, то да.
Если это все-таки круг и мы считаем, что зона приёма бинарна (либо есть, либо нет), то тогда решением будет кол-во вписанных в окружность квадратов равное площади поля. Сторона квадрата, вписанного в окружность есть радиус этой окружности. Соответсвтенно, получаем уравнение: X*Y = N*R^2 Для нашего примера: 24*18=N*6^2 N=(24*18)/(6*6)=4*3=12. Сходится? |
#5
|
||||
|
||||
Цитата:
где D - это диаметр окружности Но у меня есть подозрение, что заполнение треугольниками будет более плотным чем квадратами. Последний раз редактировалось poli-smen, 08.12.2013 в 01:13. |
#6
|
|||
|
|||
Цитата:
Да, это что-то я ошибся, невнимательно на картинку посмотрел. Тогда получается 6. Принцип тот же, только площадь вписанного квадрата = 2R^2, соответственно: X*Y = N*R^2 Для нашего примера: 24*18=N*2*6^2 N=(24*18)/(2*6*6)=2*3=6. Ну тут либо они тоже ошиблись (причем именно так же, как я), либо тут еще что-то "зарыто". А кто сказал, что должно получиться именно 12??? |
#7
|
||||
|
||||
Цитата:
И кстати, lmikle, думаю нельзя так просто делить площадь - мб не получится покрыть зону именно квадратами и придется добавлять еще точки. jmp $ ; Happy End! The Cake Is A Lie. Последний раз редактировалось Bargest, 08.12.2013 в 22:33. |
#8
|
||||
|
||||
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. Нужно значит что-то не так делать.. Но, вроде, мы где-то близко Может попробовать дополнить размеры поля до числа, которое без остатка делится на диаметр, а потом проделать эти же манипуляции?! Последний раз редактировалось M.A.D.M.A.N., 09.12.2013 в 20:00. |
#9
|
||||
|
||||
Я уже предложил, как сделать квадратами - делить отдельно длину и ширину поля, округлять результат вверх, умножать. Если сторона квадрата - 4, а поле - 7x9, то по ширине нужно 7/4 = 1 + 3/4 квадрата (округляем до 2, т.к. нужно больше 1) и по высоте 9/4 = 2 + 1/4 квадрата (округляем до 3, т.к. больше 2х). Умножаем, получаем 6 точек всего.
Однако не факт, что это оптимальное покрытие. jmp $ ; Happy End! The Cake Is A Lie. |
#10
|
||||
|
||||
У меня для 24 18 6 получилось 9, а для 24 10 6 получилось 6. Это без оптимизации
Некоторые программисты настолько ленивы, что сразу пишут рабочий код. Если вас наказали ни за что - радуйтесь: вы ни в чем не виноваты. |
#11
|
|||
|
|||
Гм. Пусть ДНА есть квадрат. При алгоритме вычисления по сторонам (округление вверх пропускаю, просто что бы не замусоривать выкладки):
N = (X\R)*(Y\R) В первом примере получается 12, А вот во втором - 8. Но это бред. Надо узнать точное условие задачи, а то как в том анекдоте про Шаляпина... |