Большой Воронежский Форум Mobile

Попалась интересная задача:

Сообщение от :
Даны действительные числа x1, x2, ... , xn, y1, y2, ... , yn, r1, r2, ... , rn. Выяснить, есть ли на плоскости точка, принадлежащая всем кругам с1, с2, ... , сn, где ci имеет центр с координатами xi, yi и радиус ri.

Трудность у меня вызвала ее метаматическая составляющая, т.е. не могу понять, при каком условии все-все эти n кругов будут иметь хотя бы одну общую точку.
Если кто знает, то подскажите плз) [Ответ]

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

А каким макаром дугу искать?) Это уж скорее не способ решения, а другая трактовка той же задачи) [Ответ]

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

просто влом расписывать в рабочее время решение давай мне ништяков какнихнибудь и я те распишу че как [Ответ]

Сообщение от SuHar`:
Трудность у меня вызвала ее метаматическая составляющая, т.е. не могу понять, при каком условии все-все эти n кругов будут иметь хотя бы одну общую точку.
Если кто знает, то подскажите плз)

чтобы тебе чутьчуть помочь с решением, могу сказать, что в басовке эту задачу лично я решал(да и после меня каждый год) в 10-м классе. еще до изучения работы с файлами в паскале(делфи). гдето 3-я четверть 10-го класса.))) [Ответ]

ГЫ, наверное ничем не помогу, но могу сказать, что те кто в басовке эту задачу решал в 10-м классе со 2-го или на худой конец 3-го курса ПММ повылетали
И все такие вот были - типа знаю как и что, но ничего не скажу, кроме того, что я крут [Ответ]

Snusmumrik, да ты крутой тип, че сказать...Только по теме бы что-нибудь написал. [Ответ]

SuHar`, ужас, ты серьёзно спрашиваешь? Имеют ли общую точку - проверяешь расстояние между двумя центрами и сумму их радиусов (если расстояние больше, то не пересекаются). Перебор по всем центрам делаешь и всё (каждого с каждым: цикл в цикле). А в принципе, это система уравнений. Просто запиши в виде уравнения координаты точки внутри круга с центром (икс1, игрек1) и радиусом эр1. Дальше объяснять? [Ответ]

Сообщение от Fanni:
ГЫ, наверное ничем не помогу, но могу сказать, что те кто в басовке эту задачу решал в 10-м классе со 2-го или на худой конец 3-го курса ПММ повылетали
И все такие вот были - типа знаю как и что, но ничего не скажу, кроме того, что я крут

Если ты ничем не поможешь, то зачем флудишь? Ты не крут, как мы поняли, зато считаешь, что крутые вылетают из ПММ... Те, кто не могут помочь, для борьбы со своими комплексами считают, что те, кто не хочет помочь, обязательно вылетят или их постигнет ещё какая неудача... Импотенция - это неспособность что-либо сделать... [Ответ]

Сообщение от Milky Man:
SuHar`, ужас, ты серьёзно спрашиваешь? Имеют ли общую точку - проверяешь расстояние между двумя центрами и сумму их радиусов (если расстояние больше, то не пересекаются). Перебор по всем центрам делаешь и всё (каждого с каждым: цикл в цикле). А в принципе, это система уравнений. Просто запиши в виде уравнения координаты точки внутри круга с центром (икс1, игрек1) и радиусом эр1. Дальше объяснять?

опередил )))))

ЗЫ
Один-в-один задачка была в школе ещё. [Ответ]

Сообщение от Fanni:
но могу сказать, что те кто в басовке эту задачу решал в 10-м классе со 2-го или на худой конец 3-го курса ПММ повылетали

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

А можно и аспирантуру пмм закончить, и потом спрашивать

Сообщение от Fanni:
Решили подключиться к Домолинку (дополнительная линия по ADSL) и к Интеркону (по технологии Ethernet).
Так вот, в железе я абсолютно не сильна. Что в себе должен иметь комп, чтобы все это работало? Тут опять два варианта.

1) пока в наличии один комп. Что надо иметь из железа, чтобы все это работало на одном компе? ADSL-модем и сетевая карта , так? Возможно есть какие-то тонкости, какую именно сетевую карту нужно приобрести?

2) планируется второй комп, он объединится с первым в сетку. В этом случае что нужно?

Спасибо

Сообщение от Fanni:
Что такое модем со встроенным свитчем? Это в прайсе как обозначается?

... [Ответ]

Сообщение от лесоруб:
Только по теме бы что-нибудь написал.

Сообщение от Milky Man:
Имеют ли общую точку - проверяешь расстояние между двумя центрами и сумму их радиусов (если расстояние больше, то не пересекаются).

надеялся, что SuHar` сам догадается, т.к. по моему представлению-человек умный... прост думал не в ту сторону. [Ответ]

Сообщение от SuHar`:
Попалась интересная задача:
Трудность у меня вызвала ее метаматическая составляющая, т.е. не могу понять, при каком условии все-все эти n кругов будут иметь хотя бы одну общую точку.
Если кто знает, то подскажите плз)

Учебник геометрии за 10-11 класс вам поможет [Ответ]

Пробовал все это в первую очередь, иначе бы и не стал спрашивать
Насчет расстояний между центрами и радиусами. С двумя кругами
это прокатит, а вот с несколькими уже не факт. Три круга например могут попарно пересекаться, но все три сразу общих точек не иметь. А насчет системы: во-первых, не уравнений, а неравенств. А во вторых, второй степени. Что-то не очень хочется с ней возиться...)))

Сообщение от Snusmumrik:
определение принадлежности точки кругу с известным центром и радиусом в частности?

не кругу, а всем кругам сразу! А если точнее нужно узнать, существует ли вообще такая точка. Неужели ты думал, что я не могу определить принадлежит ли точка кругу, записав его неравенство? [Ответ]

Сообщение от SuHar`:
Пробовал все это в первую очередь, иначе бы и не стал спрашивать
Насчет расстояний между центрами и радиусами. С двумя кругами
это прокатит, а вот с несколькими уже не факт. Три круга например могут попарно пересекаться, но все три сразу общих точек не иметь. А насчет системы: во-первых, не уравнений, а неравенств. А во вторых, второй степени. Что-то не очень хочется с ней возиться...)))
не кругу, а всем кругам сразу! А если точнее нужно узнать, существует ли вообще такая точка. Неужели ты думал, что я не могу определить принадлежит ли точка кругу, записав его неравенство?

Ну, я неправильно написал, согласен. Проверка расстояний между центрами и радиусами - необходимое условие, но не достаточное. Не уравнения, а неравенства, признаю, тоже был неправ. Тебе "не очень хочется с ней возиться"? А нам тут не лениво тебе придумывать способ попроще? Т. е. это надо через матрицы делать, но если дашь 10 баксов, то можно линейным уравнением решить?
Могу посоветовать перебор всех действительных чисел - может, это тебе будет по душе? Подставляешь в цикле во все неравенства. Берёшь числа от крайнего левого центра круга минус его радиус до крайнего праого плюс его радиус. Шаг одну миллионную или побольше и пусть компьютер считает. Находит первую точку, которая подходит всем неравенствам, выдаёт координаты и пишет, что точка существует. Устраивает, лентяй? [Ответ]

Сообщение от Milky Man:
Могу посоветовать перебор всех действительных чисел - может, это тебе будет по душе? Подставляешь в цикле во все неравенства. Берёшь числа от крайнего левого центра круга минус его радиус до крайнего праого плюс его радиус. Шаг одну миллионную или побольше и пусть компьютер считает. Находит первую точку, которая подходит всем неравенствам, выдаёт координаты и пишет, что точка существует. Устраивает, лентяй?

Если сдавать на пмм-е, то могу сразу расстроить Сухаря-\если эта задача была задана там\, то она решаться должна не так. Даже если решение(верное, оф коз) будет найдено, то задачу не примут... [Ответ]

Сообщение от Snusmumrik:
Если сдавать на пмм-е, то могу сразу расстроить Сухаря-\если эта задача была задана там\, то она решаться должна не так. Даже если решение(верное, оф коз) будет найдено, то задачу не примут...

Ущемляют прогресс! В век супербыстрых компьютеров всё надо решать перебором! Это же не 100 операций в секунду, как на старых ЭВМ! Взлом перебором всех паролей - обычное дело, почему и задачи нельзя так решать? Так появляются будущие хакеры, которые ломают пентагоновские пароли перебором. [Ответ]

Сообщение от Milky Man:
Ущемляют прогресс! В век супербыстрых компьютеров всё надо решать перебором! Это же не 100 операций в секунду, как на старых ЭВМ! Взлом перебором всех паролей - обычное дело, почему и задачи нельзя так решать? Так появляются будущие хакеры, которые ломают пентагоновские пароли перебором.

Угу, щас. Так появляются долбое.. Ох, уж этое милое поколение,мля, pepsi [Ответ]

Сообщение от shuri:
Угу, щас. Так появляются долбое.. Ох, уж этое милое поколение,мля, pepsi

Это ты кого имел ввиду? [Ответ]

1. Множество действительных чисел бесконечно.
2. Да и к тому же не счетно.
Так что не получится

эта задача была задана на ФКН)
Ладно, попробую все-таки повозиться с системой. Тем более что-то мне подсказывает, что можно ее свести к первой степени... [Ответ]

SuHar`, сегодня суббота иди пивка лучше попей, забей на задачи. [Ответ]

Сообщение от Snusmumrik:

А можно и аспирантуру пмм закончить, и потом спрашивать

...

+1024 [Ответ]

Похожая задача
http://homepages.compuserve.de/chasl...tic_info56.htm [Ответ]

Не катит.
В общем задача далеко не простая. И я уверен, что никто из отписавшихся сходу ее решить не способны, несмотря на то, что они тут говорили. Типа "мы их в 10-м классе решали". [Ответ]

Snusmumrik, расслабьтесь
Не лень же в архив влезть и поискать кто чего когда писал, я фигею.
Я и не говорила никому что я крутой программист, да я вообще не программист, и что? Проще, улыбайтесь чаще
А про басовцев, вылетающих с ПММ пачками - просто правда жизни. Задело, что ли?
Все, удаляюсь, дабы не смущать великие умы [Ответ]

Сообщение от Fanni:
А про басовцев, вылетающих с ПММ пачками - просто правда жизни. Задело, что ли?

Конечно.. обидно за своих-таки...

Сообщение от Fanni:
Не лень же в архив влезть и поискать кто чего когда писал, я фигею.

"Найти еще сообщения от Fanni" и дальше первой страницы я даже не читал)))) там еще про кошек много было...) [Ответ]

Ребята, давайте жить дружно. [Ответ]

Товарисчи, отклоняетесь от сабжа, давайте кто кричал что решал задачу, пусть даст хоть примерный сорец =) [Ответ]

Задача о точках пересечения двух окружностей расписана в учебнике геометрии в параграфе "Декартовы координаты на плоскости, уравнение окружности". Там в начало координат помещают центр первой окружности, на оси Х помещают центр другой окружности на удалении С от начала. Составляется система двух уравнений и находятся решения. Для приведенной выше задачи нужно вычислить расстояние между центрами окружностей, чтобы выявить количество точек пересечения /от 0 до 2/ и построить по описанной методе чертеж. А преобразовать координаты можно, как в предыдущем сообщении указано. сдвигом и поворотом. Сдвиг выражается простыми формулами: x2=a+x1, y2=b+Y1. Поворот на угол f - более сложными: x2= x1*sinf -y1*cosf; y2=x1*cosf +y1*sinf.

http://physics.nad.ru/cgi-bin/forum....10180&resp=166
Так сойдет? [Ответ]

Не знаю насколько оптимально, но всеже алгоритм:
1. Рассмотрим окружности с1 и с2. Найдем точку, принадлежащую пересечению этих окружностей (например, (р1+р2)/2). Назовем эту точку М1. Проверим, принадлежит, ли точка пересечению, иначе выход.
2. Рассмотрим окружность с3:
- находим уравнение прямой, проходящей через М1 и (х3;у3)
- ищем точку пересечения с окружностью с3. Точка М2
- проверяем, принадлежит ли эта точка окр. с1, с2, иначе - выход
3. Повторим п.2. для окр с4 и точки М2 и т.д.

В итоге - точка, принадлежащая всем окружностям....
Можно немного оптимизировать алгоритм, просто придумал быстро... [Ответ]