Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
В прямоугольнике с координатами левого нижнего угла (0; 0) и правого верхнего (3000; 3000) проделаны 4 дырки с координатами: (1200; 85) (63; 2500) (2700; 2650) (2990; 100) Надо найти точку, лежащую внутри прямоугольника, такую, что расстояние от нее до ближайшей от нее дырки будет максимальным. Т.е., это будет типа самая безопасная точка в прямоугольнике (в терминах возможного падения вниз и гибели). Для этих четырех конкретных дырок ответ = (1433.0; 1669.8). А если таких дырок ~1000? Как найти самую безопасную точку (хотя бы одну, если их несколько) как можно быстрее и с точностью до десятых? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 12:50 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
Реши численно. Перебором. А уточнение золотым сечением. Яб так сделал. Ведь точность большая не нужна. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 13:02 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
имхо в теориях я не силен... но может от свойств "центра тяжести" отталкнуться... Как в игрушке "Lines"... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 13:17 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
SarinРеши численно. Перебором. А уточнение золотым сечением. Яб так сделал. Ведь точность большая не нужна. Чуит мое серцо: в словах сих не токмо мудрость не по летам, но и прозорливостъ просчупываицца. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 13:31 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
Di_LIneимхо в теориях я не силен... но может от свойств "центра тяжести" отталкнуться... Как в игрушке "Lines"... Почему бы и не оттолкнуться? Можно и оттолкнуться. Только как и куда? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 13:33 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
RatTail Di_LIneимхо в теориях я не силен... но может от свойств "центра тяжести" отталкнуться... Как в игрушке "Lines"... Почему бы и не оттолкнуться? Можно и оттолкнуться. Только как и куда? имхо задачка - тонкая пластина. Дырка она и в бублике дырка. Изначально, без дырков, безопасная точка (ЦТ) в центре, на пересечении диагоналей (ЦП). Слелали дырку с известными координатами. Площадь дырки известна и "масса". Координата тож. ЦТ - смещается...Строго по прямой, проходящей через ЦП и центр дырки на растояние пропорциональное отнятой "массе" ... имхо... И так далее. Эт не матиматика, а механика чистейшей воды. имхо... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 13:40 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
Вообще-то, мои дырки - это на самом деле точки - в строгом мат. смысле. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 13:44 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
RatTailВообще-то, мои дырки - это на самом деле точки - в строгом мат. смысле. Тьфу... Я уж ножовку заточил... Тип пилить бум... Может золотые?.. Математика так математика... Бум строго мат-ругаться? - Критерий подобия есть? Есть! Применяем ТРИЗ и все увиличиваем в 1000 раз. Уже не точка, а настоящая дырка или дырочка. Пластина и так 3000 на 3000 = 900 000 точек... Слушай, как сделаешь - просвети дурилку картонную. Извини, что не по теме. Но в Лайнсе, читал где-то, именно по критерию "тяжести" алгоритм построен... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 14:00 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
Так, а как же я это сделаю, если я сам спрашиваю как это сделать? Тривиальная идея: "разбиваем прямоугольник на, скажем, 100х100 квадратов; затем разбиваем самый безопасный из этих квадратов на 100х100 более мелких квадратов и т.д." меня не привлекает. В смысле, по времени счета. Сорри, но возможную роль мифического ЦТ не догоняю. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 14:20 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
RatTailТак, а как же я это сделаю, если я сам спрашиваю как это сделать? Тривиальная идея: "разбиваем прямоугольник на, скажем, 100х100 квадратов; затем разбиваем самый безопасный из этих квадратов на 100х100 более мелких квадратов и т.д." меня не привлекает. В смысле, по времени счета. Сорри, но возможную роль мифического ЦТ не догоняю. Центр тяжести прямоугольника ну никак не будет самой безопасной точкой. Просверлим 2 дырки в где-то разных углах одной сторны. Тогда самой безопасной точкой будет где-то на середине противоположнйо стороны. Но это не центр тяжести. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 14:29 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
RatTailСорри, но возможную роль мифического ЦТ не догоняю. Он не мифический, а реальный. Возьми простой лист бумаги из принтера. Его ЦТ легко найдешь иголкой. А ЛЮБАЯ дырка - сместит его по указанной выше прямой. Это - механика и закон Всемирного тяготения... Пусть у листа 3000х3000 у одного из углов "вырезали" квадрат 100х100. ЦТ сместится в противоположную сторону от выреза. Линия перемещения будет проходить через предыдущее положение ЦТ и квази точку ЦТ выреза... Как это в матиматическую модель заложить - не по моим мозгам... Сорри... Что отвлек на глупость. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 14:30 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
Di_LIne; Я, конечно, в данный момент солидарен с Lelikk'ом, но. Можно рассмотреть идею: искомая точка находится или среди макс. удаленных от ЦТ точек или среди макс. приближенных к ЦТ точек (впрочем, это сам ЦТ). Под ЦТ можно понимать не буквально центр тяжести, а некую особую точку, которая находится достаточно легко и быстро. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 14:53 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
RatTailDi_LIne; Я, конечно, в данный момент солидарен с Lelikk'ом, но. И я не спорю... RatTailМожно рассмотреть идею: искомая точка находится или среди макс. удаленных от ЦТ точек или среди макс. приближенных к ЦТ точек (впрочем, это сам ЦТ). Под ЦТ можно понимать не буквально центр тяжести, а некую особую точку, которая находится достаточно легко и быстро. Она - ЦЕНТР (тяжести) области с координатами 1500; 1500 (по условиям примера). Ключевое слово для меня: RatTailпроделаны 4 дырки с координатами: (1200; 85) (63; 2500) (2700; 2650) (2990; 100) А если точки... Ну... Соединяем две противоположные точки линиями и получаем ответ. Так как точка пересечения этих линий и есть точка максимально удаленная от "дырок". Чистая геометрия. имхо... Если 1000 дырок... То вааще все пофиг... Соединяем любые пары "дырок" линиями... В конечном итоге получим область ГДЕ обязана быть "безопасная точка"... Конечно возможен крайний вариант... Тогда следует говорить о "выборе среднего элемента"... Это, кажется уже из бинарного поиска... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 15:07 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
Опять нифига я не понял... Ну ессно, если в припадке безумия искромсать с помощью мачете наш прямоугольник на мелкие дольки, то, конечно, искомая точка окажется в одной из полученных долек...... А может я просто туп. Окуеть. Сейчас заглянул в best solutions этой задачи. Впереди появились 11 вьетнамцев (у них - вьетнамцев - там типа мафия; не удивлюсь, если среди их 11 решений только 2 оригинальных), НО зацените их отрыв по времени от европейских решений! http://spoj.sphere.pl/ranks/RUNAWAY/ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 15:19 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
Последний технический вариант языком програмирования. Делишь все точки на 2 списка. в произвольном порядке. Поз.1 Бежишь по спискам вниз. по № в списках образуются пары точек. Находишь точку "среднего элемента." -> в третий список. Добежали до коца? Третий список делим по полам на 2 списка. Повторяем еще раз. Goto "Поз.1" Полка не останется одна точка. Блин!!! Дюже похоже на БИНАРНЫЙ ПОИСК! Или... "Сортировка слиянием"??? Что там об их быстрых циклах корифеи писали? Это тебе все намеки. Эт еще в институте проходили... или "проходили" Давай! Шай-бу! Шай-бу! Зря я что ль тут мОзги напрягаю???? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 15:32 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
По моим прикидкам таким макаром вроде бы ищется точка с мин. суммой расстояний до всех точек данного набора. Да можно хоть сто раз сказать "бинарный поиск", только кули с того. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 15:45 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
RatTailПо моим прикидкам таким макаром вроде бы ищется точка с мин. суммой расстояний до всех точек данного набора..На бумажке нарисовал. Для 10 дырок.... Имхо... расстояние от нее до ближайшей от нее дырки будет максимальным RatTailДа можно хоть сто раз сказать "бинарный поиск", только кули с того. Ну... Извини. Погорячился! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 15:52 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
Куй знает что. Я это все "понимаю". Только не понимаю, как твой алгоритм вяжется с фактом существования прямоугольной области поиска. Твои 1000 дырок висят как бы в воздухе. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 16:08 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
2 Di_LIne: ну ни фига подобного. Никто не сказал, что дырки распределены равномерно по поверхности прямоугольника. Я в одну половину запихаю 1000 дырок, в другой буедт чисто и безопасная точка даже близко не будет похожа на перечечение линий. Это вообще ничем не обоснованное предположение про соединение попарно точек. ________________________________________________________ Глюк - это высокоорганизованная система не поддающихся определению частиц ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 16:50 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
А расстояние между "безопасной точкой", и краем площади учитывать надо или нет? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 18:33 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
Ты спрашиваешь: не является ли то, что окружает снаружи наш прямоугольник, одной большой (и как бы самой опасной) Дырой и не надо ли учитывать расстояние и до этой Дыры? Что-то в этом есть. Но я не думаю, что и эту Дыру надо брать в учет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 20:38 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
Почти по сабжу, но увы совсем не то. Находит точку с минимальной суммой расстояний до точек заданного набора: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.05.2005, 23:15 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
RatTailТы спрашиваешь: не является ли то, что окружает снаружи наш прямоугольник, одной большой (и как бы самой опасной) Дырой и не надо ли учитывать расстояние и до этой Дыры? Если учитывать расстояние до краев, то получится классическая геометрическая задача вписывания максимально возможного круга. К программированию она мало относится. Решение есть в любом (наверное) учебнике по геометрии. Я ее во всяком случае встречал несколько раз. Но в общем случае метод решения достаточно простой: 1) Берешь тройку "опасных точек" и строишь окружность проходяющую через них. Если центр окружности вылез за пределы исходной площадки - подтягиваешь его. 2) Проверяешь расстояние от центра окружности до всех остальных точек. Если расстояние меньше радиуса окружности - значит эта окружность не подходит. 3) Сравниваешь все найденые окружности и та у которой радиус максимальный и будет ответом. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.05.2005, 01:20 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
забыл упомянуть :) Этот алгоритм надо применять не только к заданым в условии точкам, но и ко всем точкам образующим границу заданой площади. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.05.2005, 01:32 |
|
||
|
Опасные дырки в прямоугольнике
|
|||
|---|---|---|---|
|
#18+
>3) Сравниваешь все найденые окружности и та у которой радиус максимальный и будет ответом. Значит, ответом будет некая окружность? Слабо представляю, как "окружность" может быть ответом. С вами трудно соскучиться. То-то Кот2 рвется в аналитики, а акуз в политику. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.05.2005, 10:20 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=33044834&tid=1347687]: |
0ms |
get settings: |
10ms |
get forum list: |
21ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
162ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
69ms |
get tp. blocked users: |
1ms |
| others: | 268ms |
| total: | 550ms |

| 0 / 0 |
