Интересная задача

[SuHar`]

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

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

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

[The_God]

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

[SuHar`]

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

[The_God]

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

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

[Snusmumrik]

Сообщение от SuHar`

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

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

[Fanni]

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

[лесоруб]

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

[Milky Man]

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

[Milky Man]

Сообщение от Fanni

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

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

[mikе]

Сообщение от Milky Man

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

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

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

[Snusmumrik]

Сообщение от Fanni

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

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

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

Сообщение от Fanni

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

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

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

Спасибо

Сообщение от Fanni

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

...

[Snusmumrik]

Сообщение от лесоруб

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

Сообщение от Milky Man

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

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

[shuri]

Сообщение от SuHar`

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

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

[SuHar`]

Сообщение от Milky Man

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

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

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

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

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

[Milky Man]

Сообщение от SuHar`

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

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

[Snusmumrik]

Сообщение от Milky Man

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

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

[Milky Man]

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

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

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

[shuri]

Сообщение от Milky Man

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

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

[Milky Man]

Сообщение от shuri

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

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

[SuHar`]

Сообщение от Milky Man

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

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

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

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

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

[лесоруб]

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

[liness]

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

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


...

+1024

[Sad]

Похожая задача
http://homepages.compuserve.de/chasl...tic_info56.htm

[SuHar`]

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

[Fanni]

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

[Snusmumrik]

Сообщение от Fanni

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

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

Сообщение от Fanni

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

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

[SuHar`]

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

[mexx]

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

[shuri]

Задача о точках пересечения двух окружностей расписана в учебнике геометрии в параграфе "Декартовы координаты на плоскости, уравнение окружности". Там в начало координат помещают центр первой окружности, на оси Х помещают центр другой окружности на удалении С от начала. Составляется система двух уравнений и находятся решения. Для приведенной выше задачи нужно вычислить расстояние между центрами окружностей, чтобы выявить количество точек пересечения /от 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 и т.д.

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