Тема: Пересекаються ли окружности?
Даны n окружности. Определить пересекаются ли окружности.
Вторая задача.
Минимальная окружность, покрывающая множество точек
Re: Пересекаються ли окружности?
1. Пересекаются попарно или все вместе? Сколько окружностей?
2. Сколько точек?
Re: Пересекаються ли окружности?
Все в месте ... n <= 50000
Re: Пересекаються ли окружности?
Первую можно сделать сканирующей прямой,предварительно отсортировав все окружности по одной из координат.
Для второй,мне кажется, нужно найти пару самых отдалённых друг от друга точек.Расстояние между ними - диаметр окружности , середина отрезка ,который соединяет эти точки, - центр окружности.
Re: Пересекаються ли окружности?
coder.ua пишет:
Первую можно сделать сканирующей прямой,предварительно отсортировав все окружности по одной из координат.
Для второй,мне кажется, нужно найти пару самых отдалённых друг от друга точек.Расстояние между ними - диаметр окружности , середина отрезка ,который соединяет эти точки, - центр окружности.
Для второй задачи это не верно, даже если точки 3. Если треугольник не прямоугольный, то центр описанной окружности не будет лежать на стороне.
Насчет первой - там нужно найти точку пересечения окружностей или кругов? Если окружностей, то там все просто. Для кругов за НлогН скорее всего сканлайном, но пока не понятно как сделать так чтобы не хранить многоугольник с дугами вместо сторон и не обновлять его как-то быстро.
6 2011-02-02 11:45:55 Отредактировано Rasul Abdulaev (2011-02-02 11:48:08)
Re: Пересекаються ли окружности?
для кругов . я свел вторую задачу на первую