Дистанционная подготовка: Решётки
Решётки
от Роман Захаров - Среда 21 Ноябрь 2007, 00:32
  Пожалуйста подскажите как решать следущую задачу

Шар

В шар радиуса R помещается кубическая решетка с размером ячейки 1. Один из узлов решетки совпадает с центром шара. Таким образом, самый удалённый от центра узел может находиться на расстоянии, не большем R .

Требуется определить, сколько узлов решетки попадают внутрь шара.

Входные данные

Входной файл input.txt должен содержать одно целое число R (0<R<800).

Выходные данные

В выходной файл output.txt нужно поместить целое число – количество узлов решетки, попадающих внутрь шара.

Примеры

Пример1

input.txt

output.txt

1
7

Пример2

input.txt

output.txt

10
4169
И вобще подскажите как решать задачи такого типа аналогичная задача с окружностью!
Re: Решётки
от Владимир М. Гуровиц - Среда 21 Ноябрь 2007, 22:54
 

Ох, кажется я знаю, откуда эта задача, потому никакого желания комментировать ее не возникает. Благо тут и комментировать особо нечего и это сделали за меня: http://docs.google.com/View?docid=dd8vd82m_8dp757g

Re: Решётки
от Владимир М. Гуровиц - Среда 21 Ноябрь 2007, 22:57
  Что касается задачи про окружность, то она решается следующим образом: достаточно подсчитать, сколько точек в каждой вертикали лежит в круге. Делаем это так: Встаем в самую верхнюю точку круга и двигаемся по линиям сетки "вдоль окружности", то есть сдвигаемся на 1 вправо, затем вниз, пока не пересечем окружность, затем опять на один вправо и вниз до пересечения с коружностью. И в каждом столбце, после того, как доходим до окружности, находим количество точек (в четверти окружности). Когда дойдем до x=0, получим четверть всех точек (грубо говоря, нужно аккуратно учесть точки, лежащие на осях координат)
Re: Решётки
от Роман Захаров - Четверг 22 Ноябрь 2007, 00:35
  Насчёт самой задачи вы абсолютно правыУлыбка! Ну я просто думал там может есть какие-нибудь специальные методы решающие такие задачи!Улыбка
Спасибо за решение второй понял мне кажется эту же идею можно применить и к ШАРУ тогда будет 2-а цикла а это быстрей!
Re: Решётки
от Владимир М. Гуровиц - Четверг 22 Ноябрь 2007, 14:12
 

Конечно можно, ведь шар - это в кажом сечении такая же окружность.