Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.63
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
#1

[Матрица] Круг или квадрат? - C++

29.07.2011, 20:54. Просмотров 2449. Ответов 36
Метки нет (Все метки)

Доброго времени суток.
Условие тут.
Просьба подсказать алгоритм или выложить код с кратким описанием идеи решения.
Сам довольно много думал, но ничего дельного не надумал... А задача должна быть несложной.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2011, 20:54
Здравствуйте! Я подобрал для вас темы с ответами на вопрос [Матрица] Круг или квадрат? (C++):

Вывести на экран круг или квадрат (по выбору пользователя) - C++
Добрый день ! Помогите написать код,чтобы выводился на экрарн круг или квадрат(по выбору пользователя) по идеи нужно реализовать сами...

Написать программу, проверяющую, поместится ли круг в квадрат или наоборот. - C++
3. Заданы круг площади S и квадрат площади Р. Написать программу, проверяющую, поместится ли круг в квадрат или поместится ли квадрат в...

Определить какая из фигур – круг или квадрат - имеет большую площадь - C++
Помогите, составить программу, нужно определить какая из фигур – круг или квадрат - имеет большую площадь. Известно, что сторона...

Известны площади круга и квадрата Уместится ли круг в квадрате или квадрат в круге? - C++
2)Известны площади круга и квадрата. Определить: а) уместится ли круг в квадрат; б) уместится ли квадрат в круге.

Определить, какая из фигур (круг или квадрат) имеет большую площадь и во сколько раз (используя if) - C++
Пусть заданы две фигуры- квадрат и круг. Квадрат задан значением стороны,а круг-радиуса. Определить, какая из фигур имеет большую площадь...

Квадрат,круг,стрелка,ромб - C++
Здравствуйте,помогите написать программу,которая выводит на монитор следующие изображения:Квадрат,круг,стрелка,ромб. Спасибо заранее! :)

36
easybudda
Модератор
Эксперт CЭксперт С++
9680 / 5630 / 954
Регистрация: 25.07.2009
Сообщений: 10,807
29.07.2011, 21:09 #2
diagon, а по-моему всё просто: если все угловые клетки пустые - круг, если хоть одна занята - квадрат... Хотя может и не так всё на самом деле, первое, что на ум пришло...
"Угловые клетки" - 1 1; 1 4; 4 1; 4 4
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
29.07.2011, 21:13  [ТС] #3
Цитата Сообщение от easybudda Посмотреть сообщение
diagon, а по-моему всё просто: если все угловые клетки пустые - круг, если хоть одна занята - квадрат... Хотя может и не так всё на самом деле, первое, что на ум пришло...
"Угловые клетки" - 1 1; 1 4; 4 1; 4 4
Так ведь их все можно закрасить, и угловые и стороны.
Поэтому я и затрудняюсь, слишком рандомные получаются фигуры.
Да и не я один, эту задачу всего 6 человек сдали =)
0
Daemon025
380 / 329 / 67
Регистрация: 06.12.2010
Сообщений: 900
30.07.2011, 00:29 #4
diagon, попробуй сравнить стороны фигуры, если равны, то квадрат
1
grizlik78
Эксперт С++
1963 / 1456 / 118
Регистрация: 29.05.2011
Сообщений: 3,015
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
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 09:38 #6
Находим матрицу минимального размера NxN
Если N < 3 - КРУГ
Если N == 3 - КВАДРАТ
Сканируем центральную подматрицу размером (N-2)x(N-2).
Если хоть одна клетка пуста - КРУГ.

Добавлено через 2 минуты
Алгоритм построения КРУГА не определён, поэтому нужно сканировать всю внутреннюю матрицу, а не только края. Т.е. кругом вполне может быть дрявый квадрат.
1
-=ЮрА=-
Заблокирован
Автор FAQ
30.07.2011, 10:56 #7
Я думаю необходим замер объекта по горизонтали, вертикали (по осям фигуры) и по прямым проходящим под углом 45 градусов к осям координат (назову их диагонали). Таким образом отнесение фигуры к квадрату или к кругу можно осуществить при сравнени диагоналей с осями фигуры. Если диагонали составляют к примеру К = 0,75 от осей то это круг, если более то квадрат. При этом коэффициент К можно подобрать методом проб и ошибок.
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 11:04  [ТС] #8
Daemon025, так они же рандомные, могут и не совпадать.

grizlik78, а почему именно 9 клеток? Квадрат же может быть любого размера(но не меньше 3).

Deviaphan, спасибо, хороший вариант...
Однако есть небольшая проблемка...
Если клетки возле квадрата вообще не закрашены, то вторую и n - 2ую строку/столбец будет считать за валидную, даже есть дырки есть, т.к. минимальная область немного неправильно определиться.
-=ЮрА=-, рандомно как-то, там же не 1 тест, сложно будет найти коэффициент, который под все тесты подходит.
0
grizlik78
Эксперт С++
1963 / 1456 / 118
Регистрация: 29.05.2011
Сообщений: 3,015
30.07.2011, 11:09 #9
Цитата Сообщение от diagon Посмотреть сообщение
а почему именно 9 клеток? Квадрат же может быть любого размера(но не меньше 3).
только эти 9 клеток отстоят не дальше чем на 2 от левой верхней границы. Ну с правой нижней мы сравниваем сами, как я уже говорил. Алгоритм не так сложно реализовать, а главное, он проходит все тесты

Добавлено через 2 минуты
Эти 9 клеток это всего лишь левый угол девяти разных квадратов. Как-минимум один из этих квадратов должен целиком включать в себя неизменяемый квадрат (если исходно был квадрат). Это я и проверяю своим алгоритмом. Дырявый квадрат будет принят за круг.
1
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 11:25  [ТС] #10
А, ну да...
Но все равно остается проблема - как правильно определить минимальную матрицу, ведь соседние с квадратом клетки могут вообще не закрашиваться... Или вы это не учитывали, и у вас все равно прошло?

Впрочем, перечитал условие, такого быть не должно. Буду реализовывать.
0
grizlik78
Эксперт С++
1963 / 1456 / 118
Регистрация: 29.05.2011
Сообщений: 3,015
30.07.2011, 11:26 #11
Цитата Сообщение от diagon Посмотреть сообщение
Но все равно остается проблема - как правильно определить минимальную матрицу, ведь соседние с квадратом клетки могут вообще не закрашиваться... Или вы это не учитывали, и у вас все равно прошло?
Погоди, что-то проблему я не понял до конца. Посмотрим на зашумлённый квадрат в задаче
Название: image.asp.gif
Просмотров: 47

Размер: 2.1 Кб
допустим мы определили, что минимальный прямоугольник, включающий все чёрные клетки, это
квадрат с координатами (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
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 11:31  [ТС] #12
Цитата Сообщение от grizlik78 Посмотреть сообщение
Погоди, что-то проблему я не понял до конца.
Да меня просто смутила эта строка в условии
некоторые клетки, граничащие с квадратом (на рисунке обозначены цифрой 2), закрашиваются черным.
Т.к. не указано обратного, то хотябы одна клетка должна быть закрашенной.
0
grizlik78
Эксперт С++
1963 / 1456 / 118
Регистрация: 29.05.2011
Сообщений: 3,015
30.07.2011, 11:35 #13
Если бы исходный квадрат совсем не изменялся, или сжался бы до квадрата 2x2 или превратился бы в прямоугольник — во всех случаях алгоритм отработает правильно, так как неизменный внутренний квадрат обязательно целиком войдёт хотя бы в один из 9 проверяемых квадратов.

Добавлено через 2 минуты
Цитата Сообщение от diagon Посмотреть сообщение
Т.к. не указано обратного, то хотябы одна клетка должна быть закрашенной.
Ну, в общем-то не важно, сколько клеток закрашивается, сколько стирается. И то и другое может изменяться от 0 до максимального значения. На работоспособность моего алгоритма это не влияет.
1
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 11:40  [ТС] #14
Цитата Сообщение от grizlik78 Посмотреть сообщение
На работоспособность моего алгоритма это не влияет.
Мне немного больше приглянулся алгоритм от Deviaphan т.к. его реализация будет покороче, но для него нужно точно определить минимальную матрицу(включая соседние с квадратом клетки), а я не знаю как это сделать, если квадрат не измениться. Воспользуюсь вашим. Спасибо.
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 11:47 #15
Цитата Сообщение от diagon Посмотреть сообщение
но для него нужно точно определить минимальную матрицу
А в чём проблема? Сканируешь все строки и сохраняешь индексы минимальной и максимальной ячеек. Вот тебе и минимальная матрица. Это наименее сложная часть алгоритма.)
Если извратиться, можно вообще за один проход всё реализовать. Но лучше за два, чтобы проще.
0
30.07.2011, 11:47
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2011, 11:47
Привет! Вот еще темы с ответами:

Определить, когда круг и квадрат касаются (пересекаются) - C++
подскажите пожалуйста как определить когда круг и квадрат касаются (пересекаются)

Выведено изображение, нужно на нем нарисовать по фигуру (квадрат, круг) - C++
Выведено изображение, нужно на нем нарисовать по фигуру (квадрат, круг). размер и положение я должен выбрать.

Построить классы для описания плоских фигур:круг,квадрат,прямоугольник - C++
Построить классы для описания плоских фигур:круг,квадрат,прямоугольник.Включить методы для определения периметра и площади...

Известны площади круга и квадрата. Определить: а)местится ли круг в квадрате б)уместится ли квадрат в круге - C++
Известны площади круга и квадрата. Определить: а)местится ли круг в квадрате б)уместится ли квадрат в круге /* Заданы площади круга...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru