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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

Что-то в этом есть. Но я не думаю, что и эту Дыру надо брать
в учет.
...
Рейтинг: 0 / 0
02.05.2005, 23:15
    #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
03.05.2005, 01:20
    #33045245
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Опасные дырки в прямоугольнике
RatTailТы спрашиваешь:
не является ли то, что окружает снаружи наш прямоугольник,
одной большой (и как бы самой опасной) Дырой и не надо ли
учитывать расстояние и до этой Дыры?
Если учитывать расстояние до краев, то получится классическая геометрическая задача вписывания максимально возможного круга. К программированию она мало относится. Решение есть в любом (наверное) учебнике по геометрии. Я ее во всяком случае встречал несколько раз.

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

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

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


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