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

@testosteron · Регистрация: 17.05.2014

Студворк — интернет-сервис помощи студентам

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

@jetyb · 15.11.2014, 19:53

Как ее решать:
1) Понятно, что задача сводится к системе неравенств для x, y:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?(x - x_i)^2 + (y-y_i)^2 \leq r_i^2$
Надо просто проверить ее решаемость.
2) Если область пересечения существует, то для какого-то круга точки его границы принадлежат пересечению.
Это самый маленький круг (докажите сами).
Значит для самого маленького $https://www.cyberforum.ru/cgi-bin/latex.cgi?r_k$ неравенство превращается в равенство.
3) Преобразуем неравенства, оставив слева квадраты:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?x^2 + y^2 <= a_1\cdot x + b_1\cdot x + c_1,\quad i\neq r$
и вычтем из каждого неравенства равенство для $https://www.cyberforum.ru/cgi-bin/latex.cgi?r_k$
4) Квадраты пропадут. Получится уже система на n-1 линейных неравенств на x и y. Это уже стандартная решаемая задача линейного программирования. Ее можно решить например симплекс-методом или вышеизложенным приемом.

@ViterAlex · 16.11.2014, 06:59

jetyb, мне непонятно второе утверждение. Поясните рисунком или доказательством

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

@jetyb · 16.11.2014, 09:08

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

Это самый маленький круг

Хм, ну тут я ошибся. Это не так.

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

Если область пересечения существует, то для какого-то круга точки его границы принадлежат пересечению.

Это достаточно очевидно, доказывается например индукцией.
1) у пересечения 1 круга его граница принадлежит пересечению
2) если пересечение n-1 кругов U содержит границы какого-то круга , то следующий круг либо содержит U либо пересекает U своей границей. В обоих случаях в пересечении есть граница какого-то круга.

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

@ViterAlex · 16.11.2014, 09:37

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

@jetyb · 16.11.2014, 09:42

http://imgdisk.ru/image/n77

Новые блоги и статьи Все статьи Все блоги /
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .

@testosteron 0 / 0 / 0 Регистрация: 17.05.2014 Сообщений: 10

	.NET 4.x Выяснить, есть ли на плоскости точка, принадлежащая всем кругам 15.11.2014, 19:21. Показов 1934. Ответов 5 Метки нет (Все метки) Даны действительные числа x1, x2, ... , xn, y1, y2, ... , yn, r1, r2, ... , rn. Выяснить, есть ли на плоскости точка, принадлежащая всем кругам с1, с2, ... , сn, где ci имеет центр с координатами xi, yi и радиус ri. 0

@jetyb 296 / 259 / 107 Регистрация: 26.10.2012 Сообщений: 809
	15.11.2014, 19:53
	Как ее решать: 1) Понятно, что задача сводится к системе неравенств для x, y: $https://www.cyberforum.ru/cgi-bin/latex.cgi?(x - x_i)^2 + (y-y_i)^2 \leq r_i^2$ Надо просто проверить ее решаемость. 2) Если область пересечения существует, то для какого-то круга точки его границы принадлежат пересечению. Это самый маленький круг (докажите сами). Значит для самого маленького $https://www.cyberforum.ru/cgi-bin/latex.cgi?r_k$ неравенство превращается в равенство. 3) Преобразуем неравенства, оставив слева квадраты: $https://www.cyberforum.ru/cgi-bin/latex.cgi?x^2 + y^2 <= a_1\cdot x + b_1\cdot x + c_1,\quad i\neq r$ и вычтем из каждого неравенства равенство для $https://www.cyberforum.ru/cgi-bin/latex.cgi?r_k$ 4) Квадраты пропадут. Получится уже система на n-1 линейных неравенств на x и y. Это уже стандартная решаемая задача линейного программирования. Ее можно решить например симплекс-методом или вышеизложенным приемом. 1

@ViterAlex 8951 / 4863 / 1886 Регистрация: 11.02.2013 Сообщений: 10,246
	16.11.2014, 06:59
	jetyb, мне непонятно второе утверждение. Поясните рисунком или доказательством 0

@ViterAlex 8951 / 4863 / 1886 Регистрация: 11.02.2013 Сообщений: 10,246
	16.11.2014, 09:37
	Мне кажется, тут задача сводится к тому, чтобы определить, что все круги пересекаются, т.е. нет такой пары кругов, расстояние между центрами которых больше суммы их радиусов. Если так, значит такая точка существует 0

@jetyb 296 / 259 / 107 Регистрация: 26.10.2012 Сообщений: 809
	16.11.2014, 09:42
	http://imgdisk.ru/image/n77 0