powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Опасные дырки в прямоугольнике
25 сообщений из 68, страница 1 из 3
Опасные дырки в прямоугольнике
    #33044760
Фотография RatTail
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В прямоугольнике
с координатами левого нижнего угла (0; 0) и правого верхнего (3000; 3000)
проделаны 4 дырки с координатами:
(1200; 85)
(63; 2500)
(2700; 2650)
(2990; 100)

Надо найти точку, лежащую внутри прямоугольника, такую, что расстояние от
нее до ближайшей от нее дырки будет максимальным. Т.е., это будет типа самая
безопасная точка в прямоугольнике (в терминах возможного падения вниз и гибели).

Для этих четырех конкретных дырок ответ = (1433.0; 1669.8).
А если таких дырок ~1000?
Как найти самую безопасную точку (хотя бы одну, если их несколько) как можно
быстрее и с точностью до десятых?
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044778
Sarin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Реши численно. Перебором. А уточнение золотым сечением. Яб так сделал. Ведь точность большая не нужна.
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044790
Фотография Di_LIne
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
имхо в теориях я не силен...
но может от свойств "центра тяжести" отталкнуться...
Как в игрушке "Lines"...
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044805
Фотография RatTail
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SarinРеши численно. Перебором. А уточнение золотым сечением. Яб так сделал. Ведь точность большая не нужна.
Чуит мое серцо: в словах сих не токмо мудрость не по летам, но и прозорливостъ просчупываицца.
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044806
Фотография RatTail
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Di_LIneимхо в теориях я не силен...
но может от свойств "центра тяжести" отталкнуться...
Как в игрушке "Lines"...
Почему бы и не оттолкнуться? Можно и оттолкнуться. Только как и куда?
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044809
Фотография Di_LIne
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RatTail Di_LIneимхо в теориях я не силен...
но может от свойств "центра тяжести" отталкнуться...
Как в игрушке "Lines"...
Почему бы и не оттолкнуться? Можно и оттолкнуться. Только как и куда? имхо задачка - тонкая пластина.
Дырка она и в бублике дырка. Изначально, без дырков, безопасная точка (ЦТ)
в центре, на пересечении диагоналей (ЦП). Слелали дырку с известными
координатами. Площадь дырки известна и "масса". Координата тож.
ЦТ - смещается...Строго по прямой, проходящей через ЦП и центр дырки
на растояние пропорциональное отнятой "массе" ... имхо...
И так далее.
Эт не матиматика, а механика чистейшей воды. имхо...
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044813
Фотография RatTail
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вообще-то, мои дырки - это на самом деле точки - в строгом мат. смысле.
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044826
Фотография Di_LIne
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RatTailВообще-то, мои дырки - это на самом деле точки - в строгом мат. смысле. Тьфу... Я уж ножовку заточил... Тип пилить бум...
Может золотые?.. Математика так математика...
Бум строго мат-ругаться?
- Критерий подобия есть? Есть!
Применяем ТРИЗ и все увиличиваем в 1000 раз.
Уже не точка, а настоящая дырка или дырочка.
Пластина и так 3000 на 3000 = 900 000 точек...

Слушай, как сделаешь - просвети дурилку картонную.
Извини, что не по теме. Но в Лайнсе, читал где-то, именно по критерию
"тяжести" алгоритм построен...
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044834
Фотография RatTail
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Так, а как же я это сделаю, если я сам спрашиваю как это сделать?
Тривиальная идея: "разбиваем прямоугольник на, скажем, 100х100 квадратов;
затем разбиваем самый безопасный из этих квадратов на 100х100 более мелких
квадратов и т.д." меня не привлекает. В смысле, по времени счета.

Сорри, но возможную роль мифического ЦТ не догоняю.
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044842
Фотография Lelikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RatTailТак, а как же я это сделаю, если я сам спрашиваю как это сделать?
Тривиальная идея: "разбиваем прямоугольник на, скажем, 100х100 квадратов;
затем разбиваем самый безопасный из этих квадратов на 100х100 более мелких
квадратов и т.д." меня не привлекает. В смысле, по времени счета.

Сорри, но возможную роль мифического ЦТ не догоняю.

Центр тяжести прямоугольника ну никак не будет самой безопасной точкой.
Просверлим 2 дырки в где-то разных углах одной сторны. Тогда самой безопасной точкой будет где-то на середине противоположнйо стороны. Но это не центр тяжести.
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044843
Фотография Di_LIne
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RatTailСорри, но возможную роль мифического ЦТ не догоняю. Он не мифический, а реальный. Возьми простой лист бумаги из принтера.
Его ЦТ легко найдешь иголкой. А ЛЮБАЯ дырка - сместит его по указанной
выше прямой. Это - механика и закон Всемирного тяготения...
Пусть у листа 3000х3000 у одного из углов "вырезали" квадрат 100х100.
ЦТ сместится в противоположную сторону от выреза. Линия перемещения
будет проходить через предыдущее положение ЦТ и квази точку ЦТ выреза...
Как это в матиматическую модель заложить - не по моим мозгам...
Сорри... Что отвлек на глупость.
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044858
Фотография RatTail
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Di_LIne;

Я, конечно, в данный момент солидарен с Lelikk'ом, но.
Можно рассмотреть идею: искомая точка находится или среди макс. удаленных
от ЦТ точек или среди макс. приближенных к ЦТ точек (впрочем, это сам ЦТ).

Под ЦТ можно понимать не буквально центр тяжести, а некую особую точку,
которая находится достаточно легко и быстро.
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044870
Фотография Di_LIne
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RatTailDi_LIne;
Я, конечно, в данный момент солидарен с Lelikk'ом, но. И я не спорю...

RatTailМожно рассмотреть идею: искомая точка находится или среди макс. удаленных
от ЦТ точек или среди макс. приближенных к ЦТ точек (впрочем, это сам ЦТ).

Под ЦТ можно понимать не буквально центр тяжести, а некую особую точку,
которая находится достаточно легко и быстро.
Она - ЦЕНТР (тяжести) области с координатами 1500; 1500 (по условиям примера).
Ключевое слово для меня: RatTailпроделаны 4 дырки с координатами:
(1200; 85)
(63; 2500)
(2700; 2650)
(2990; 100)

А если точки...
Ну... Соединяем две противоположные точки линиями и получаем ответ.
Так как точка пересечения этих линий и есть точка максимально удаленная от
"дырок". Чистая геометрия. имхо...
Если 1000 дырок... То вааще все пофиг...
Соединяем любые пары "дырок" линиями...
В конечном итоге получим область ГДЕ обязана быть "безопасная точка"...
Конечно возможен крайний вариант...
Тогда следует говорить о "выборе среднего элемента"...
Это, кажется уже из бинарного поиска...
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044874
Фотография RatTail
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Опять нифига я не понял... Ну ессно, если в припадке безумия искромсать с помощью мачете наш прямоугольник на мелкие дольки, то, конечно, искомая точка окажется в одной из полученных долек...... А может я просто туп.

Окуеть. Сейчас заглянул в best solutions этой задачи. Впереди появились 11 вьетнамцев (у них - вьетнамцев - там типа мафия; не удивлюсь, если среди их 11 решений только 2 оригинальных), НО зацените их отрыв по времени от европейских решений! http://spoj.sphere.pl/ranks/RUNAWAY/
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044881
Фотография Di_LIne
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Последний технический вариант языком програмирования.
Делишь все точки на 2 списка. в произвольном порядке.
Поз.1

Бежишь по спискам вниз. по № в списках образуются пары точек.
Находишь точку "среднего элемента." -> в третий список.
Добежали до коца?
Третий список делим по полам на 2 списка.
Повторяем еще раз. Goto "Поз.1"

Полка не останется одна точка.


Блин!!! Дюже похоже на БИНАРНЫЙ ПОИСК!
Или... "Сортировка слиянием"???

Что там об их быстрых циклах корифеи писали?
Это тебе все намеки.
Эт еще в институте проходили... или "проходили"

Давай! Шай-бу! Шай-бу!
Зря я что ль тут мОзги напрягаю????
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044900
Фотография RatTail
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По моим прикидкам таким макаром вроде бы ищется точка с мин. суммой расстояний до всех точек данного набора.

Да можно хоть сто раз сказать "бинарный поиск", только кули с того.
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044907
Фотография Di_LIne
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RatTailПо моим прикидкам таким макаром вроде бы ищется точка с мин. суммой расстояний до всех точек данного набора..На бумажке нарисовал. Для 10 дырок....
Имхо... расстояние от нее до ближайшей от нее дырки будет максимальным

RatTailДа можно хоть сто раз сказать "бинарный поиск", только кули с того. Ну... Извини. Погорячился!
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044918
Фотография RatTail
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Куй знает что. Я это все "понимаю".
Только не понимаю, как твой алгоритм вяжется с фактом существования
прямоугольной области поиска. Твои 1000 дырок висят как бы в воздухе.
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33044956
Фотография Lelikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
2 Di_LIne: ну ни фига подобного.
Никто не сказал, что дырки распределены равномерно по поверхности прямоугольника. Я в одну половину запихаю 1000 дырок, в другой буедт чисто и безопасная точка даже близко не будет похожа на перечечение линий.
Это вообще ничем не обоснованное предположение про соединение попарно точек.
________________________________________________________
Глюк - это высокоорганизованная система не поддающихся определению частиц
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33045021
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А расстояние между "безопасной точкой", и краем площади учитывать надо или нет?
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33045111
Фотография RatTail
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ты спрашиваешь:
не является ли то, что окружает снаружи наш прямоугольник,
одной большой (и как бы самой опасной) Дырой и не надо ли
учитывать расстояние и до этой Дыры?

Что-то в этом есть. Но я не думаю, что и эту Дыру надо брать
в учет.
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33045186
Фотография RatTail
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Почти по сабжу, но увы совсем не то.
Находит точку с минимальной суммой расстояний до точек заданного набора:
Код: 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.
Sub Distance_Min_Sum()
Const N =  3     'число точек в наборе
Dim p(1 To N, 1 To 2), i&, j&, ds#, sx#, sy#, ss#, x#, y#

p(1, 1) = 0: p(1, 2) = 0         '( 0 ;  0 )
p( 2 ,  1 ) =  2 : p( 2 ,  2 ) =  0          '(2; 0)
p(3, 1) = 1: p(3, 2) = 10000     '( 1 ;  10000 )

For i =  1  To N
x = x + p(i,  1 )
Next i
x = x / N    '0-ое приближение: X равен ср. арифметическому Xi
For i = 1 To N
y = y + p(i, 2)
Next i
y = y / N    '0-ое приближение: Y равен ср. арифметическому Yi

For j =  1  To  500     'число итераций
sx = 0: sy = 0: ss = 0
For i = 1 To N
ss = ss + 1 / Sqr((p(i, 1) - x) ^ 2 + (p(i, 2) - y) ^ 2)
Next i
For i = 1 To N
sx = sx + p(i, 1) / Sqr((p(i, 1) - x) ^ 2 + (p(i, 2) - y) ^ 2)
Next i
x = sx / ss    'j-ое приближение для X целевой точки
For i =  1  To N
sy = sy + p(i,  2 ) / Sqr((p(i,  1 ) - x) ^  2  + (p(i,  2 ) - y) ^  2 )
Next i
y = sy / ss    'j-ое приближение для Y целевой точки
Next j

'находим сумму расстояний ds и выводим результат
For i =  1  To N
ds = ds + Sqr((p(i,  1 ) - x) ^  2  + (p(i,  2 ) - y) ^  2 )
Next i
MsgBox x & vbCrLf & y & vbCrLf & ds
End Sub
Ответ для этих трех точек немного неожиданный: (1; 0.577).
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33045245
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
RatTailТы спрашиваешь:
не является ли то, что окружает снаружи наш прямоугольник,
одной большой (и как бы самой опасной) Дырой и не надо ли
учитывать расстояние и до этой Дыры?
Если учитывать расстояние до краев, то получится классическая геометрическая задача вписывания максимально возможного круга. К программированию она мало относится. Решение есть в любом (наверное) учебнике по геометрии. Я ее во всяком случае встречал несколько раз.

Но в общем случае метод решения достаточно простой:
1) Берешь тройку "опасных точек" и строишь окружность проходяющую через них. Если центр окружности вылез за пределы исходной площадки - подтягиваешь его.
2) Проверяешь расстояние от центра окружности до всех остальных точек. Если расстояние меньше радиуса окружности - значит эта окружность не подходит.
3) Сравниваешь все найденые окружности и та у которой радиус максимальный и будет ответом.
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33045249
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
забыл упомянуть :)
Этот алгоритм надо применять не только к заданым в условии точкам, но и ко всем точкам образующим границу заданой площади.
...
Рейтинг: 0 / 0
Опасные дырки в прямоугольнике
    #33045507
Фотография RatTail
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
>3) Сравниваешь все найденые окружности и та у которой радиус максимальный и будет ответом.

Значит, ответом будет некая окружность?
Слабо представляю, как "окружность" может быть ответом.

С вами трудно соскучиться. То-то Кот2 рвется в аналитики, а акуз в политику.
...
Рейтинг: 0 / 0
25 сообщений из 68, страница 1 из 3
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Опасные дырки в прямоугольнике
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]