|
Вопрос # 249/ вопрос открыт / |
|
Люди плиз помогите с задачкой.
[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 (статус: Посетитель)
Вопрос отправлен: 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
Комментарий к оценке: Большое спасибо!
|
Мини-форум вопроса
Мини-форум пуст.
Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.
|
