Higher
|
|
1 | |
[Матрица] Круг или квадрат?29.07.2011, 20:54. Показов 5968. Ответов 36
Метки нет (Все метки)
Доброго времени суток.
Условие тут. Просьба подсказать алгоритм или выложить код с кратким описанием идеи решения. Сам довольно много думал, но ничего дельного не надумал... А задача должна быть несложной.
0
|
29.07.2011, 20:54 | |
Ответы с готовыми решениями:
36
Вывести на экран круг или квадрат (по выбору пользователя) Написать программу, проверяющую, поместится ли круг в квадрат или наоборот. Определить какая из фигур – круг или квадрат - имеет большую площадь Известны площади круга и квадрата Уместится ли круг в квадрате или квадрат в круге? |
Модератор
12458 / 7482 / 1753
Регистрация: 25.07.2009
Сообщений: 13,762
|
|
29.07.2011, 21:09 | 2 |
diagon, а по-моему всё просто: если все угловые клетки пустые - круг, если хоть одна занята - квадрат... Хотя может и не так всё на самом деле, первое, что на ум пришло...
"Угловые клетки" - 1 1; 1 4; 4 1; 4 4
0
|
Higher
|
|
29.07.2011, 21:13 [ТС] | 3 |
Так ведь их все можно закрасить, и угловые и стороны.
Поэтому я и затрудняюсь, слишком рандомные получаются фигуры. Да и не я один, эту задачу всего 6 человек сдали =)
0
|
382 / 330 / 159
Регистрация: 06.12.2010
Сообщений: 894
|
|
30.07.2011, 00:29 | 4 |
diagon, попробуй сравнить стороны фигуры, если равны, то квадрат
1
|
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
|
|
30.07.2011, 01:11 | 5 |
Не знаю, может я пока и не самый простой алгоритм придумал, но по-крайней мере рабочий.
1. Определяем минимальную прямоугольную область (x1, y1, x2, y2) которая включает в себя все закрашенные клетки. 2. Определяем для проверки 9 клеток с координатами x1 <= x < x+3 и y1 <= y < y+3 3. Для каждой из 9 координат (x, y) находим максимальный квадрат с левым верхним углом в клетке (x, y) и состоящий только из закрашенных клеток. 4. Если хотя бы для одного квадрата правая и нижняя стороны отстоят не дальше чем на 2 клетки от x2 и y2 соответственно, то это мог быть квадрат. Иначе нет.
1
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
30.07.2011, 09:38 | 6 |
Находим матрицу минимального размера NxN
Если N < 3 - КРУГ Если N == 3 - КВАДРАТ Сканируем центральную подматрицу размером (N-2)x(N-2). Если хоть одна клетка пуста - КРУГ. Добавлено через 2 минуты Алгоритм построения КРУГА не определён, поэтому нужно сканировать всю внутреннюю матрицу, а не только края. Т.е. кругом вполне может быть дрявый квадрат.
1
|
Заблокирован
|
|
30.07.2011, 10:56 | 7 |
Я думаю необходим замер объекта по горизонтали, вертикали (по осям фигуры) и по прямым проходящим под углом 45 градусов к осям координат (назову их диагонали). Таким образом отнесение фигуры к квадрату или к кругу можно осуществить при сравнени диагоналей с осями фигуры. Если диагонали составляют к примеру К = 0,75 от осей то это круг, если более то квадрат. При этом коэффициент К можно подобрать методом проб и ошибок.
0
|
Higher
|
|
30.07.2011, 11:04 [ТС] | 8 |
Daemon025, так они же рандомные, могут и не совпадать.
grizlik78, а почему именно 9 клеток? Квадрат же может быть любого размера(но не меньше 3). Deviaphan, спасибо, хороший вариант... Однако есть небольшая проблемка... Если клетки возле квадрата вообще не закрашены, то вторую и n - 2ую строку/столбец будет считать за валидную, даже есть дырки есть, т.к. минимальная область немного неправильно определиться. -=ЮрА=-, рандомно как-то, там же не 1 тест, сложно будет найти коэффициент, который под все тесты подходит.
0
|
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
|
|
30.07.2011, 11:09 | 9 |
только эти 9 клеток отстоят не дальше чем на 2 от левой верхней границы. Ну с правой нижней мы сравниваем сами, как я уже говорил. Алгоритм не так сложно реализовать, а главное, он проходит все тесты
Добавлено через 2 минуты Эти 9 клеток это всего лишь левый угол девяти разных квадратов. Как-минимум один из этих квадратов должен целиком включать в себя неизменяемый квадрат (если исходно был квадрат). Это я и проверяю своим алгоритмом. Дырявый квадрат будет принят за круг.
1
|
Higher
|
|
30.07.2011, 11:25 [ТС] | 10 |
А, ну да...
Но все равно остается проблема - как правильно определить минимальную матрицу, ведь соседние с квадратом клетки могут вообще не закрашиваться... Или вы это не учитывали, и у вас все равно прошло? Впрочем, перечитал условие, такого быть не должно. Буду реализовывать.
0
|
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
|
|
30.07.2011, 11:26 | 11 |
Погоди, что-то проблему я не понял до конца. Посмотрим на зашумлённый квадрат в задаче
допустим мы определили, что минимальный прямоугольник, включающий все чёрные клетки, это квадрат с координатами (1, 6), (1, 6) ищем максимальные квадраты из 9 левых верхних точек. из (1, 1) квадрат со стороной 1 из (1, 2) квадрат со стороной 0 из (1, 3) квадрат со стороной 2 из (2, 1) квадрат со стороной 0 из (2, 2) квадрат со стороной 2 из (2, 3) квадрат со стороной 2 из (3, 1) квадрат со стороной 0 из (3, 2) квадрат со стороной 1 из (3, 3) квадрат со стороной 2 Среди этих квадратов есть один, правая нижняя граница которого отстоит не дальше 2 клеток от правой и от нижней границ прямоугольной области. Это квадрат (3, 3), (4, 4). Значит эту картинку можно получить из квадрата. Теперь, какие есть варианты, когда алгоритм будет работать неправильно?
0
|
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
|
|
30.07.2011, 11:35 | 13 |
Если бы исходный квадрат совсем не изменялся, или сжался бы до квадрата 2x2 или превратился бы в прямоугольник — во всех случаях алгоритм отработает правильно, так как неизменный внутренний квадрат обязательно целиком войдёт хотя бы в один из 9 проверяемых квадратов.
Добавлено через 2 минуты Ну, в общем-то не важно, сколько клеток закрашивается, сколько стирается. И то и другое может изменяться от 0 до максимального значения. На работоспособность моего алгоритма это не влияет.
1
|
Higher
|
|
30.07.2011, 11:40 [ТС] | 14 |
Мне немного больше приглянулся алгоритм от Deviaphan т.к. его реализация будет покороче, но для него нужно точно определить минимальную матрицу(включая соседние с квадратом клетки), а я не знаю как это сделать, если квадрат не измениться. Воспользуюсь вашим. Спасибо.
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
30.07.2011, 11:47 | 15 |
А в чём проблема? Сканируешь все строки и сохраняешь индексы минимальной и максимальной ячеек. Вот тебе и минимальная матрица. Это наименее сложная часть алгоритма.)
Если извратиться, можно вообще за один проход всё реализовать. Но лучше за два, чтобы проще.
0
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||||||
30.07.2011, 12:08 | 16 | |||||
Да, я вчера тоже к этому алгоритму пришел.
Одна из возможных реализаций:
2
|
Higher
|
||||||
30.07.2011, 18:38 [ТС] | 17 | |||||
Был немного занят...
Попробовал реализовать оба варианта, оба не получилось >_> Допустим, будет такой тест: *** *.* *** Т.к. проверка на дырки не идет по последним двум сторонам, то оба алгоритма считают это квадратом. Собственно, про это и был мой вопрос... Более коротким кстати оказался вариант от grizlik78, только я немного по другому к нему подошел. Зачем строить кучу квадратов, если интересует только один, одна из вершин которого находиться в правом нижнем углу? Поэтому я строю только один квадрат, одна вершина которого находиться в одной из 9 точек, другая - правый нижний угол предполагаемого квадрата. Если его возможно построить, то смотрю, есть ли в нем дырки, иначе перехожу к следующей точке. Но он получает Wrong Answer на 6 тесте. Да и как он будет работать с вышеприведенным примером я не представляю... Собственно, код:
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
30.07.2011, 18:50 | 18 |
Если K равно 3, то все ячейки должны быть заполнены для квадрата. Просто дополни условие.
0
|
Higher
|
|
30.07.2011, 19:00 [ТС] | 19 |
А если 3x4/4x3/4x4/etc ? Для всех случаев дополнительное условие писать?
P.S. исправил мелкую опечатку в коде, теперь Wrong Answer уже на 5 тесте(был на 6м) xD
0
|
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
|
|
30.07.2011, 19:03 | 20 |
Квадратом это не могло являться только из-за ограниченности поля и размера квадрата. Для большего поля, с достаточным количеством свободного пространства вокруг, такую фигуру вполне можно получить из квадрата 3x3.
К счастью, такого теста там нет (либо ответ SQUARE для него считается правильным, что, конечно, не верно). Обработка граничных условий сильно бы осложнила алгоритм.
0
|
30.07.2011, 19:03 | |
30.07.2011, 19:03 | |
Помогаю со студенческими работами здесь
20
Определить, какая из фигур (круг или квадрат) имеет большую площадь и во сколько раз (используя if) Квадрат,круг,стрелка,ромб Определить, когда круг и квадрат касаются (пересекаются) Выведено изображение, нужно на нем нарисовать по фигуру (квадрат, круг) Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |