Экспертная система Delphi.int.ru

Сообщество программистов
Общение, помощь, обмен опытом

Логин:
Пароль:
Регистрация | Забыли пароль?

Delphi.int.ru Expert

Другие разделы портала

Переход к вопросу:

#   

Статистика за сегодня:  


Лучшие эксперты

Подробнее »



Вопрос # 249

Раздел: Delphi » Прочее
/ вопрос открыт /

Люди плиз помогите с задачкой.

[Quote]На шахматной доске размером N на N размещен круг с радиусом R так, что его центр совпадаетс центром одной из клеток. Требуется посчитать количевство белых и черных клеток доски, целиком попавших внутрь круга. Левая нижняя клетка доски - черная.
Входные данные (circle.in):
На первой строке входного файла даны 4 целых числа, разделенные пробелом: N - размер стороны доски (1<=100), R - радиус круга (1<=R<=100). X, Y - координаты
клеток центр которой совпадает с центром круга (1<=X,Y<=N). Координаты клетокотсчитываются от левой нижней клетки доски, которая имеет координаты (1,1).
Выходные данные (circle):
В выходной файл нужно вывести два целых числа - количевство белых и черных клеток которые попали внутрь круга.[/Quote]

Я ее уже дня два решаю и... ничего.

Желательно на паскале но можно и на delphi.
Заранее спасибо!

AlexKZ Вопрос ожидает решения (принимаются ответы, доступен мини-форум)

Вопрос задал: AlexKZ (статус: Посетитель)
Вопрос отправлен: 9 января 2007, 12:50
Состояние вопроса: открыт, ответов: 1.

Ответ #1. Отвечает эксперт: Вадим К

Алгоритм простой до безобразия. Но как обычно в алгебре, нужно лишь точно задать систему координат
Пусть сторона квадрата клетки имеет размер 1 еденицу. Тогда координаты первой клетки такие
(0.0)
(0,1)
(1,0)
(1,1)

Для произвольной клетки координаты будут такие
(x,y)
(x+1,y)
(x,y+1)
(x+1,y+1)

Теперь круг. он у нас рисуется с центра клетки, поэтому координаты должны просчитываться так
(x+0.5,y+0.5)

Здесь у меня x и y координаты клетки (по номерам, а не в новой системе координат)

Теперь споминаем геометрию, которая говорит, что если есть круг с центром в точке (x,y), радиуса R и точка (a,b), то точка будет внутри круга, если выполняется условия
R^2>(x-a)^2+(y-b)^2
^2 - это "в квадрате". По поводу равно надо ещё подумать, так как вещественные числа сравнивать на равенство нельзя, и как быть, когда точка находиться на окружности.

и предпоследнее - как определить цвет клетки.
если клетка (1,1) чёрная, то
если mod(x-y)mod 2=0 то эта клетка также чёрная
Если 1 - белая.

Теперь у нас всё есть. Можно алгоритм писать.
Заводим две переменные для количества белых и чёрных клеток. Обнуляем их.
делаем двойной цикл, что бы оббежать по всем клеткам.
в цыкле
Вычисляем координаты 4 вершин текущей клетки и проверяем, попадают ли они в круг. Если все четыре вершины попали, значит и клетка попадает. Почему - докажите сами.
Если попали - вычисляем цвет клетки и увеличиваем соответствующую переменную.
Хотя, если мы пробегаем последовательно по всем клеткам, то цвета будут постоянно чередоваться.

Код не привожу - это удовольствие оставляю для вас :)

Ответ отправил: Вадим К (статус: Академик)
Время отправки: 9 января 2007, 17:20
Оценка за ответ: 5

Комментарий к оценке: Большое спасибо!

Мини-форум вопроса

Мини-форум пуст.

Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.

Версия движка: 2.6+ (26.01.2011)
Текущее время: 24 февраля 2020, 11:45
Выполнено за 0.02 сек.
Рейтинг@Mail.ru