Технический форум

Технический форум (http://www.tehnari.ru/)
-   Помощь студентам (http://www.tehnari.ru/f41/)
-   -   Блок-схема (http://www.tehnari.ru/f41/t104952/)

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 (Сообщение 1172413)
Расстояние между центрами R = ( x1 - x2 ) * ( x1 - x2 ) + ( y1 - y2 ) * ( y1 - y2 )

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

Сообщение от MagentaTiger (Сообщение 1172413)
Пересекаются если
R <= ( r1 + r2 ) * ( r1 + r2 ) И
((r1 > r2 И R >= r1 - r2) ИЛИ (r1 <= r2 И r2 - r1 ))

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

Сообщение от MagentaTiger (Сообщение 1172413)
Если пересекаются то счетчик пересекающихся окружностей увеличиваем на 1

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

MagentaTiger 26.10.2015 13:17

Цитата:

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

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

Vladimir_S 26.10.2015 14:03

Цитата:

Сообщение от MagentaTiger (Сообщение 1172435)
Но надо учесть частные случаи когда одна окружность внутри другой но при этом не пересекают друг друга

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


Часовой пояс GMT +4, время: 03:56.

Powered by vBulletin® Version 4.5.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.