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

[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 четверти координатной плоскости):
**
***
***
****
как мы видим, при проходе слева направо высота столбцов убывает, то есть если в 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