Задан прямоугольник axb. моль проела в нем n дырок-точек. найти круг наибольшей площади, несъеденный молью. на окружности есть точки дырки. 

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

Двусмысленность. Уточните пожалуйста.

причём тут с++?
алгоритмы обсуждают здесь: http://forum.vingrad.ru/forum/tech-algorit...que-method.html

Это сообщение отредактировал(а) zim22 - 25.3.2009, 17:31

  

Сначала покажите мне моль, которая будет жрать прямоугольник. 

зы. А потом я вам отвечу - что прямая дорога и моли, и прямоугольнику, и variag в Центр Помощи.

Зачет! +1

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

вы читать умеете? вы темой ошиблись. единственное на что вы можете рассчитывать - это отрицательную репутацию.

Задан ковер прямоугольной формы  (axb). моль проела в нем n дырок, считаем точками. найти круг наибольшей площади, несъеденный молью. на границу попадает часть этих точек. 

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

Да да да... +1.

Товарисчу, создавшему тему, стоило бы поставить -1, но...

Во-первых, недостаточно этих проверок. Т.к. искомый круг может ещё ограничиваться точкой и двумя сторонами прямоугольника, или двумя точками и одной стороной. Т.е. помимо рассмотрения всех троек точек надо ещё и такие сочетания рассматривать.

Во-вторых, асимптотика этого алгоритма - n^4. Это много? (просто вы же не указали ограничения на n). Эта задача не выглядит простой, в том смысле, что более быстрый алгоритм, если и есть, то очень сложен (имхо).

Есть такая штука - триангуляция Делоне. Она характерна тем, что для любого треугольника окружность, его описывающая, не содержит внутри других точек. Т.е. надо на заданных точках (включая углы прямоугольника) построить триангуляцию Делоне и среди всех окружностей, описывающих треугольники, найти окружность максимального радиуса.
Построение триангуляции Делоне - интересный, но не тривиальный алгоритм, например тут: http://algolist.manual.ru/maths/geom/deluanay.php

ЗЫ: модераторы, перенесите плиз тему....

 zim22, хоть вы и 22...,  слова по уточнению  относились не к вам, т.к. в свою ошибку я признал.

 baldina,  спасибо!

Он это понял. Просто хотел напомнить Вам, уважаемый, что Вы темой ошиблись.

обе темы объединил, можно продолжить обсуждение самого алгоритма 

Нужная точка имеет координаты (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)  - радиус

Проще говоря надо найти пару точек, расстояние между которыми максимально возможное, 
но меньше расстояния до любой заданной в условии точки и границ прямоугольника.

Осталось решить квадратичные неравенства с квадратичной целевой функцией
   

еще 5 тыщ вёдер, и ключик у нас в кармане.