| Вопрос: Задачка: Окружность и клетки | Добавлено: 24.04.05 03:04 |
Автор вопроса:  Morpheus | Web-сайт: xury.zx6.ru
|
|
Задана окружность на "клечатой бумаге".
Окружность задана координатами центра и радиусом. Найти количество клеток, которые полностью лежат внутри окружности. Решение знаю только приблезительно и только теоретически. сейчас попробую сделать для начал сам. |
| Ответы | Всего ответов: 9 |
|
Номер ответа: 1 Автор ответа:  GSerg Вопросов: 0 Ответов: 1876 
|
Профиль | | #1 | Добавлено: 24.04.05 04:46 |
|
Окружность есть что?
Геометрическое место точек, равноудалённых от центра. Посему: Берём квадрат со стороной, равной диаметру окружности. Короче, описанный вокруг окружности квадрат берём. Для каждой клетки из этого квадрата проверяем, не лежат ли все 4 вершины клетки внутри окружности. Вершина считается внутри окружности, если расстояние от неё до центра окружности не больше радиуса окружности. Запоминаем клетки, все вершины которых удовлетворяют этому условию... |
||
|
Номер ответа: 2 Автор ответа: MorpheusВопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #2 | Добавлено: 24.04.05 04:52 |
|
Угу, мне кажется такое решение катит.
Только мне кажется, что можно проверять только одну вершину, то есть внешнюю, но похоже легче организовать перебор четырёх вершин, чем высчитывать относительно четверти, какая из вершин внешняя. А поначалу я голову ломал над этой задачкой 
|
||
|
Номер ответа: 3 Автор ответа: GSergВопросов: 0 Ответов: 1876
|
Профиль | | #3 | Добавлено: 24.04.05 05:48 |
|
Представь, что горизонтальный радиус окружности делит сетку пополам между квадратами. Тогда у разделённых квадратов будет две "внешние" вершины
|
||
|
Номер ответа: 4 Автор ответа: MorpheusВопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #4 | Добавлено: 24.04.05 06:44 |
|
угу.
Наверное всё таки надо решать твоим методом. Даёт 128% гарантию, не меньше
Да кстати, кто нить решал ещё задачу шарпа с полками и книгами? |
||
|
Номер ответа: 5 Автор ответа: GSergВопросов: 0 Ответов: 1876
|
Профиль | | #5 | Добавлено: 24.04.05 07:53 |
|
Смотрел
Посчитал, сколько будет вариантов на 1000 книг (а будет около 3E+300), после чего подумал, что сначала узнать лимит книг было бы полезно
|
||
|
Номер ответа: 6 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #6 | Добавлено: 24.04.05 10:35 |
|
Тогда у разделённых квадратов будет две "внешние" вершины Расстояние-то до них будет одинаковое.
|
||
|
Номер ответа: 7 Автор ответа: GSergВопросов: 0 Ответов: 1876
|
Профиль | | #7 | Добавлено: 24.04.05 10:59 |
|
1. Только если радиус делит квадраты точно пополам.
2. Всё равно этот факт сложнее определить, чем просто посчитать расстояния от четырёх вершин до центра
|
||
|
Номер ответа: 8 Автор ответа: MorpheusВопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #8 | Добавлено: 24.04.05 17:11 |
|
Да всётаки точку то можно хоть где ставить.
А перебирать как? от минус до плюс бесконечности? наверное надо пределы в условии записать 
|
||
|
Номер ответа: 9 Автор ответа: GSergВопросов: 0 Ответов: 1876
|
Профиль | | #9 | Добавлено: 24.04.05 18:39 |
|
Предел - радиус окружности, я ж сказал
|
||
Страница: 1 |