Цитата(variag @ 25.3.2009, 17:09  ) |
| на окружности есть точки дырки. |
Двусмысленность. Уточните пожалуйста.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > задача про ковер и моль |
| Автор: variag 25.3.2009, 17:09 |
| Задан прямоугольник axb. моль проела в нем n дырок-точек. найти круг наибольшей площади, несъеденный молью. на окружности есть точки дырки. Мне кажется, что можно взять три точки составить уравнение окружности, проходящей через эти точки. Потом другие три точки и сравнивать радиусы. Только перебор...... |
| Автор: andrew_121 25.3.2009, 17:26 | ||
Двусмысленность. Уточните пожалуйста. |
| Автор: zim22 25.3.2009, 17:29 |
| причём тут с++? алгоритмы обсуждают здесь: http://forum.vingrad.ru/forum/tech-algorithm-techique-method.html |
| Автор: mrbrooks 25.3.2009, 17:31 |
 Сначала покажите мне моль, которая будет жрать прямоугольник. зы. А потом я вам отвечу - что прямая дорога и моли, и прямоугольнику, и variag в Центр Помощи. |
| Автор: andrew_121 25.3.2009, 17:37 | ||
Зачет! +1 |
| Автор: variag 25.3.2009, 18:04 |
| уточняю, ковер прямоугольной формы, дырки считаем точечными. нужно вырезать круг наибольшей площади, граница его проходит через часть этих точек, а внутрь не попадает ни одной. замечание по поводу обращения не по адресу принято |
| Автор: zim22 25.3.2009, 18:09 | ||
вы читать умеете? вы темой ошиблись. единственное на что вы можете рассчитывать - это отрицательную репутацию. |
| Автор: variag 25.3.2009, 18:09 |
| Задан ковер прямоугольной формы (axb). моль проела в нем n дырок, считаем точками. найти круг наибольшей площади, несъеденный молью. на границу попадает часть этих точек. Мне кажется, что можно взять три точки составить уравнение окружности, проходящей через эти точки. Потом другие три точки и сравнивать радиусы. Только перебор...... |
| Автор: andrew_121 25.3.2009, 18:25 | ||
Да да да... +1. Товарисчу, создавшему тему, стоило бы поставить -1, но... |
| Автор: maxdiver 25.3.2009, 18:28 |
| Во-первых, недостаточно этих проверок. Т.к. искомый круг может ещё ограничиваться точкой и двумя сторонами прямоугольника, или двумя точками и одной стороной. Т.е. помимо рассмотрения всех троек точек надо ещё и такие сочетания рассматривать. Во-вторых, асимптотика этого алгоритма - n^4. Это много? (просто вы же не указали ограничения на n). Эта задача не выглядит простой, в том смысле, что более быстрый алгоритм, если и есть, то очень сложен (имхо). |
| Автор: baldina 25.3.2009, 20:19 |
| Есть такая штука - триангуляция Делоне. Она характерна тем, что для любого треугольника окружность, его описывающая, не содержит внутри других точек. Т.е. надо на заданных точках (включая углы прямоугольника) построить триангуляцию Делоне и среди всех окружностей, описывающих треугольники, найти окружность максимального радиуса. Построение триангуляции Делоне - интересный, но не тривиальный алгоритм, например тут: http://algolist.manual.ru/maths/geom/deluanay.php ЗЫ: модераторы, перенесите плиз тему.... |
| Автор: variag 25.3.2009, 20:42 |
| zim22, хоть вы и 22..., слова по уточнению относились не к вам, т.к. в свою ошибку я признал. baldina, спасибо! |
| Автор: andrew_121 26.3.2009, 11:33 | ||
Он это понял. Просто хотел напомнить Вам, уважаемый, что Вы темой ошиблись. |
| Автор: maxim1000 26.3.2009, 23:24 |
обе темы объединил, можно продолжить обсуждение самого алгоритма  |
| Автор: Ivanovich 31.3.2009, 15:29 |
| Нужная точка имеет координаты (xc, yc), другие точки (x1, y1) ... (xn, yn). Тогда квадрат расстояния от точки (xc, yc) до некоторой точки(x, y) будет (x - xc)^2 + (y - yc)^2. Нужно найти максимум из минимумов расстояний Max(Min(R1, ...., Rn)) для всех точек из прямоугольника Область значений (x, y) для некоторой точки (xc, yc) (x - xc)^2 + (y - yc)^2 < (x1 - xc)^2 + (y1 - yc)^2 .............. (x - xc)^2 + (y - yc)^2 < (xn - xc)^2 + (yn - yc)^2 xc - x > 0 x - xc < MX // x от 0 до максимума yc - y > 0 y - yc < MY // y от 0 до максимума Целевая функция (x - xc)^2 + (y - yc)^2 -> Max Результат (xc, yc) - точка, sqrt((x - xc)^2 + (y - yc)^2) - радиус Проще говоря надо найти пару точек, расстояние между которыми максимально возможное, но меньше расстояния до любой заданной в условии точки и границ прямоугольника. Осталось решить квадратичные неравенства с квадратичной целевой функцией  |
| Автор: baldina 31.3.2009, 15:32 |
еще 5 тыщ вёдер, и ключик у нас в кармане.  |