Тема: Пересекаються ли окружности?
Даны n окружности. Определить пересекаются ли окружности.
Вторая задача.
Минимальная окружность, покрывающая множество точек
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Пересекаються ли окружности?
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Даны n окружности. Определить пересекаются ли окружности.
Вторая задача.
Минимальная окружность, покрывающая множество точек
1. Пересекаются попарно или все вместе? Сколько окружностей?
2. Сколько точек?
Все в месте ... n <= 50000
Первую можно сделать сканирующей прямой,предварительно отсортировав все окружности по одной из координат.
Для второй,мне кажется, нужно найти пару самых отдалённых друг от друга точек.Расстояние между ними - диаметр окружности , середина отрезка ,который соединяет эти точки, - центр окружности.
Первую можно сделать сканирующей прямой,предварительно отсортировав все окружности по одной из координат.
Для второй,мне кажется, нужно найти пару самых отдалённых друг от друга точек.Расстояние между ними - диаметр окружности , середина отрезка ,который соединяет эти точки, - центр окружности.
Для второй задачи это не верно, даже если точки 3. Если треугольник не прямоугольный, то центр описанной окружности не будет лежать на стороне.
Насчет первой - там нужно найти точку пересечения окружностей или кругов? Если окружностей, то там все просто. Для кругов за НлогН скорее всего сканлайном, но пока не понятно как сделать так чтобы не хранить многоугольник с дугами вместо сторон и не обновлять его как-то быстро.
для кругов . я свел вторую задачу на первую
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Пересекаються ли окружности?