Задачка про окружность, Помогите.............. Опции

[BETTI]

На плоскости задана окружность радиуса R с центром в точке (X, Y), где X, Y, R – вещественные числа (│X│ ≤ 1000, │Y│ ≤ 1000, R ≤ 1000). Определить, сколько целочисленных единичных квадратиков, то есть, квадратиков со сторонами единичной длины (координаты вершин этих квадратиков являются целыми числами), лежит внутри заданной окружности.

Пример:
Ввод:
4.4 (Х)
-1 (Y)
2.5 ®
Вывод:
10

Сообщение отредактировано: BETTI - 23.11.2007 19:19

[мисс_граффити]

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

но хотелось бы:
1) узнать источник задачи
2) посмотреть мысли автора темы

[BETTI]

Источник????
Преподаватель дала условие, а откуда, не знаю......

с точки зрения математики, я думала, что её надо решать так:
х-координата абсциссы
у -координата ординаты
1)х-1 (х- расстояние от нач коорд до центра окр + радиус )
2) проводим прямую, перпендикулярную Ох
3) К этой прямой проводим проекция ( т е перпендикуляр) длинной 1
Получаем две параллельные прямые , расстояние между которыми 1
4) Разбиваем эту"ленту" на клеточки
.............и т д


Но , мне кажется, можно решить её проще, только вот не могу придумать как.....

[мисс_граффити]

Ну, во-первых, будем работать не со всей окружностью, а с ее четвертью.
Представим ее столбцами (ну вот как-то так - четверть окружности с центром в начале координат, соотв 1 четверти координатной плоскости):
**
***
***
****
как мы видим, при проходе слева направо высота столбцов убывает, то есть если в n-ном столбце m целочисленных точек (точку, лежащую на оси, не считаем), то между ним и n-1 будет m квадратиков.
сколько целочисленных точек в первом столбике - мы знаем (y0=trunc®)
во втором столбце координата х1=1
проверим, попадет ли точка (x1,y0) в наш круг. Если попала - отлично, количество квадратиков первого столбца знаем (y0). y1=y0. иначе - y1=y0-1. опять проверяем, пока не попадет.
Переходим на следующий. x2=2...
и так, пока хn<>trunc®
разумеется, столько переменных вводить не надо. это я для наглядности
-----
это если центр в начале координат
надо подумать, что изменится при смещении центра

Сообщение отредактировано: мисс_граффити - 24.11.2007 1:18