Блок-схема

smetaninaanna · 26.10.2015, 10:31

Помогите составить блок схему.
Даны целые числа x1, y1, r1, …, xn, yn, rn, которые задают последовательность окружностей так, что (xi,yi) – координаты центра окружности, ri – радиус окружности. Вывести количество окружностей, не имеющих пересечений с другими.

MagentaTiger · 26.10.2015, 11:34

Вам математику или именно блок схему (просто рисовать лень

)
Математика же проста, надо в цикле от 1 до N
Проверить пересекается ли текущая в по номеру окружность со всеми остальными (для этого нужен естественно второй внутренний цикл)
пересечение проверяем следующим образом
Расстояние между центрами
R = ( x1 - x2 ) * ( x1 - x2 ) + ( y1 - y2 ) * ( y1 - y2 )
Пересекаются если
R <= ( r1 + r2 ) * ( r1 + r2 ) И
((r1 > r2 И R >= r1 - r2) ИЛИ (r1 <= r2 И R>=r2 - r1 ))
Если пересекаются то счетчик пересекающихся окружностей увеличиваем на 1

Vladimir_S · 26.10.2015, 12:56

Олег, ну чего наворотил?

Цитата:

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

Расстояние между центрами R = ( x1 - x2 ) * ( x1 - x2 ) + ( y1 - y2 ) * ( y1 - y2 )

Точнее, так:
Если R - расстояние между центрами, то
R² = (x1-x2)² + (y1-y2)²

Цитата:

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

Пересекаются если
R <= ( r1 + r2 ) * ( r1 + r2 ) И
((r1 > r2 И R >= r1 - r2) ИЛИ (r1 <= r2 И r2 - r1 ))

Да зачем так сложно? Пересекаются, если R < (r1 + r2). Всё, больше ничего не надо.

Цитата:

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

Если пересекаются то счетчик пересекающихся окружностей увеличиваем на 1

Точнее, так. Увеличиваем счетчик окружностей, НЕ пересекающих другие, если при прохождении внутреннего цикла не случилось ни одного пересечения. Если случилось - цикл следует прервать.

MagentaTiger · 26.10.2015, 13:17

Цитата:

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

Да зачем так сложно? Пересекаются, если R < (r1 + r2). Всё, больше ничего не надо.

Ну маленько намудрил

Но надо учесть частные случаи когда одна окружность внутри другой но при этом не пересекают друг друга

Кстати задачки интересные, видно на олимпиаду готовится

Vladimir_S · 26.10.2015, 14:03

Цитата:

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

Но надо учесть частные случаи когда одна окружность внутри другой но при этом не пересекают друг друга

А! Тогда да, правильно. Я почему-то решил, что речь о кругах с общей площадью.

26.10.2015, 10:31	#1 (permalink)
smetaninaanna Новичок Регистрация: 26.10.2015 Сообщений: 2 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	Блок-схема Помогите составить блок схему. Даны целые числа x1, y1, r1, …, xn, yn, rn, которые задают последовательность окружностей так, что (xi,yi) – координаты центра окружности, ri – радиус окружности. Вывести количество окружностей, не имеющих пересечений с другими.

26.10.2015, 10:31
Helpmaster Member Регистрация: 08.03.2016 Сообщений: 0	Ранее созданных обсуждения помогут раскрыть глаза на решение проблемы Блок-схема Блок-схема Блок-схема

26.10.2015, 11:34	#2 (permalink)
MagentaTiger Специалист Регистрация: 27.04.2015 Адрес: Москва Сообщений: 1,423 Записей в дневнике: 4 Сказал(а) спасибо: 52 Поблагодарили 53 раз(а) в 16 сообщениях Репутация: 18120	Вам математику или именно блок схему (просто рисовать лень ) Математика же проста, надо в цикле от 1 до N Проверить пересекается ли текущая в по номеру окружность со всеми остальными (для этого нужен естественно второй внутренний цикл) пересечение проверяем следующим образом Расстояние между центрами R = ( x1 - x2 ) * ( x1 - x2 ) + ( y1 - y2 ) * ( y1 - y2 ) Пересекаются если R <= ( r1 + r2 ) * ( r1 + r2 ) И ((r1 > r2 И R >= r1 - r2) ИЛИ (r1 <= r2 И R>=r2 - r1 )) Если пересекаются то счетчик пересекающихся окружностей увеличиваем на 1

Ads
Яндекс Member Регистрация: 31.10.2006 Сообщений: 40200 Записей в дневнике: 0 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 55070