| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [Алгоритм] задачка |
| Автор: Reptor 5.10.2009, 10:53 |
| Встретил вот такую задачу Подсчитать количество точек с целочисленными координатами, которые попадают в R>0. центр в начале координат. что то я не понял.. их же бесконечность... или нет? |
| Автор: Bitter 5.10.2009, 11:01 |
| Ну точек вообще - да. С целочисленными координатами (например X = 2, Y = 3) - конечное число Ну можно сделать так (хотя, наверное, не лучший алгоритм): 1. Находим сначала приблизительную область компромисов. А именно Xmin = Округлить(- R); Xmax = Округлить( R ); Ymin = Xmin; Ymax = Xmax; После этого у Вас будет квадрат из (Xmax-Xmin)*(Ymax-Ymin) целочисленных точек. 2. Находим область компромисов перебором Если (Xmin+i)*(Xmin+i)+(Ymin+j)*(Ymin+j) <= R*R, то эта точка входит в область компромисов. i изменяется от 0 до Xmax-Xmin, j от 0 до Ymax-Ymin Типа того |
| Автор: SoWa 5.10.2009, 13:35 |
| Область перебора, предложенного Bitterом можно сократить. Перебирать только те точки, которые находятся в сгменте окуржности. А сегменты построить вот как: Bitter предложил вариант квадрата, а можно взять ромб, вершинами которого будут являться округленные точки(окружность предполагает центр в начале координат). В картинке нарисовано. А можно наверно вообще, думаю, триангулировать окружность(треугольники с вершинами в целых координатах) и решение готово. |
| Автор: Void 5.10.2009, 13:56 |
| http://mathworld.wolfram.com/GausssCircleProblem.html |
| Автор: SoWa 5.10.2009, 14:09 |
| Умные дядьки придумали все до нас |
| Автор: v2v 5.10.2009, 18:02 | ||
какое элементарно красивое решение. надо взять на заметку. |
