Показать сообщение отдельно
Старый 20.01.2012, 20:17   #31
Igor
Мастер
 
Аватар для Igor
 
Регистрация: 03.05.2010
Адрес: Подмосковье
Сообщений: 1,218
Написано 438 полезных сообщений
(для 790 пользователей)
Ответ: Олимпиада по программированию

Идеи:
1) Круг неспроста. Пусть x,y-координаты середины кольца с радиусом R. Тогда для любой точки S=sqrt((X-Xточки)^2+(Y-Yточки)^2), модуль разности |S-R| должен быть одинаковым для всех точек-тогда мы решили задачу.
2) Если через эти четыре точки можно провести окружность, то ответ - Infinity, координаты центра окружности и радиус=0
В пункте 2 мы исключили варианты, когда все точки либо снаружи либо внутри.
3) Возможный вариант: Три точки лежат снаружи (или 3 внутри), а четвёртая - с другой стороны от дороги.
Берём три точки, ищем центр проходящей через них окружности, (радиус Ra), расстояние от центра до четвёртой точки Rb, возможный вариант решения (R=(Ra+Rb)/2)
смотрим для всех вариантов троек (их 4) и выбираем наименьший R
4) Последний вариант - две точки снаружи и две внутри. Пусть у нас две пары (1 и 2) и (3 и 4). проводим прямую равноудалённую от 1 и 2 (между ними), и прямую, равноудалённую от 3 и 4. Пересечение прямых - центр окружности. R=среднее арифметическое расстояний от центра до т. 1 и до т. 3
Для всех вариантов пар точек ищем наименьший R.
5) Ответ- вариант с наименьшим R из пунктов 3 и 4 если не прокатило со вторым
__________________
О¯О ¡¡¡ʁɔvʎнdǝʚǝdǝu dиW
(Offline)
 
Ответить с цитированием
Эти 2 пользователя(ей) сказали Спасибо Igor за это полезное сообщение:
Nerd (20.01.2012), Nikich (11.07.2013)