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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Добавлено через 2 минуты
Цитата Сообщение от diagon Посмотреть сообщение
Т.к. не указано обратного, то хотябы одна клетка должна быть закрашенной.
Ну, в общем-то не важно, сколько клеток закрашивается, сколько стирается. И то и другое может изменяться от 0 до максимального значения. На работоспособность моего алгоритма это не влияет.
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 11:40  [ТС]     [Матрица] Круг или квадрат? #14
Цитата Сообщение от grizlik78 Посмотреть сообщение
На работоспособность моего алгоритма это не влияет.
Мне немного больше приглянулся алгоритм от Deviaphan т.к. его реализация будет покороче, но для него нужно точно определить минимальную матрицу(включая соседние с квадратом клетки), а я не знаю как это сделать, если квадрат не измениться. Воспользуюсь вашим. Спасибо.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 11:47     [Матрица] Круг или квадрат? #15
Цитата Сообщение от diagon Посмотреть сообщение
но для него нужно точно определить минимальную матрицу
А в чём проблема? Сканируешь все строки и сохраняешь индексы минимальной и максимальной ячеек. Вот тебе и минимальная матрица. Это наименее сложная часть алгоритма.)
Если извратиться, можно вообще за один проход всё реализовать. Но лучше за два, чтобы проще.
Mr.X
Эксперт С++
3042 / 1687 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
30.07.2011, 12:08     [Матрица] Круг или квадрат? #16
Цитата Сообщение от grizlik78 Посмотреть сообщение
Не знаю, может я пока и не самый простой алгоритм придумал, но по-крайней мере рабочий.
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 соответственно, то это мог быть квадрат. Иначе нет.
Да, я вчера тоже к этому алгоритму пришел.
Одна из возможных реализаций:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector<int>    T_row;
typedef std::vector<T_row>  T_matr;
/////////////////////////////////////////////////////////////////////////////////////////
bool  is_square
    (
        int            rows_total,
        int            cols_total,
        const T_matr&  matr
    )
{
    const int  SQUARE_DIM_MIN  = 3;
    const int  MATR_DIM_MAX    = 1000;
    if(std::min(rows_total, cols_total) < SQUARE_DIM_MIN) return false;
    if(std::max(rows_total, cols_total) > MATR_DIM_MAX  ) return false;
    bool  black_cell_exist = false;
    //Отыскиваем минимальный прямоугольник, содержащий все черные клетки
    //(расширяя область, если встречаем черную клетку).
    int  left_not_white_col    = cols_total;
    int  right_not_white_col   = -1;
 
    int  top_not_white_row     = rows_total;
    int  bottom_not_white_row  = -1;
 
    for(int  row = 0; row < rows_total; ++row)
    {
        for(int  col = 0; col < cols_total; ++col)
        {
            if(matr[row][col])
            {
                black_cell_exist = true;
 
                if(col < left_not_white_col)
                {
                    left_not_white_col = col;    
                }
 
                if(col > right_not_white_col)
                {
                    right_not_white_col = col;    
                }
 
                if(row < top_not_white_row)
                {
                    top_not_white_row = row;    
                }
 
                if(row > bottom_not_white_row)
                {
                    bottom_not_white_row = row;    
                }
            }//if
        }//for(int  col = 0; col < rows_total; ++col)
    }//for(int  row = 0; row < rows_total; ++row)
 
    if(!black_cell_exist) return false;
 
    //Вычисляем размеры полученного прямоугольника.
    int  not_white_W = right_not_white_col  - left_not_white_col + 1;
    int  not_white_H = bottom_not_white_row - top_not_white_row  + 1;
    //Вычисляем минимальную сторону оставшегося квадрата.
    int  remaind_square_W    = std::max(1, not_white_W - 4);
    int  remaind_square_H    = std::max(1, not_white_H - 4);
    int  remaind_square_dim  = std::max(remaind_square_W, remaind_square_H);
 
    //Пробегаемся по левым верхним допустимым вершинам оставшегося квадрата.
    for(int  top_sq_row = top_not_white_row; 
        top_sq_row <= top_not_white_row + 2; 
        ++top_sq_row)
    {
        //Если до нижнего края прямоугольника не больше 2, то:        
        if(bottom_not_white_row - (top_sq_row + remaind_square_dim - 1) <= 2)
        {
            for(int  left_sq_col = left_not_white_col; 
                left_sq_col <= left_not_white_col + 2; 
                ++left_sq_col)
            {
                //Если до правого края прямоугольника не больше 2, то:                
                if(right_not_white_col - (left_sq_col + remaind_square_dim - 1) <= 2)
                {
                    //Проверяем, что все клетки квадрата черные.
                    bool  remaind_square_is_black = true;
                    for(int  rem_sq_row = top_sq_row; 
                        rem_sq_row < top_sq_row + remaind_square_dim;
                        ++ rem_sq_row)
                    {
                        for(int  rem_sq_col = left_sq_col; 
                            rem_sq_col < left_sq_col + remaind_square_dim;
                            ++ rem_sq_col)
                        {
                            if(!matr[rem_sq_row][rem_sq_col])
                            {
                                remaind_square_is_black = false;
                            }
                        }                    
                    }
                    if(remaind_square_is_black)  return true;
                }
            }            
        }
    }
    return  false;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    const int  ARR_DIM = 7;
    int  arr[ARR_DIM][ARR_DIM] =
    {
        {0, 0, 0, 0, 0, 0, 0},
 
        {0, 0, 0, 0, 0, 0, 0},
 
        {0, 0, 0, 0, 1, 0, 0},
 
        {0, 0, 0, 0, 0, 0, 0},
 
        {0, 0, 1, 0, 0, 0, 0},
 
        {0, 0, 0, 0, 0, 0, 0},
 
        {0, 0, 0, 0, 0, 0, 0},
    };
 
    T_matr  matr(ARR_DIM, T_row(ARR_DIM));
    for(int  i = 0; i < ARR_DIM; ++i)
    {
        for(int  j = 0; j < ARR_DIM; ++j)
        {
            matr[i][j] = arr[i][j];
        }
    }
    std::cout << (is_square(ARR_DIM, ARR_DIM, matr) ? "квадрат" : "круг")
              << std::endl;
}
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 18:38  [ТС]     [Матрица] Круг или квадрат? #17
Был немного занят...
Попробовал реализовать оба варианта, оба не получилось >_>
Допустим, будет такой тест:
***
*.*
***
Т.к. проверка на дырки не идет по последним двум сторонам, то оба алгоритма считают это квадратом. Собственно, про это и был мой вопрос...
Более коротким кстати оказался вариант от grizlik78, только я немного по другому к нему подошел. Зачем строить кучу квадратов, если интересует только один, одна из вершин которого находиться в правом нижнем углу? Поэтому я строю только один квадрат, одна вершина которого находиться в одной из 9 точек, другая - правый нижний угол предполагаемого квадрата. Если его возможно построить, то смотрю, есть ли в нем дырки, иначе перехожу к следующей точке. Но он получает Wrong Answer на 6 тесте. Да и как он будет работать с вышеприведенным примером я не представляю...
Собственно, код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstdlib> //for abs
int main(){
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n, m;
    std::cin >> n >> m;
    if (n < 3 || m < 3){
        std::cout << "CIRCLE";
        return 0;
    }
    char **matrix = new char* [n];
    for (int i = 0; i < n; ++i)
        matrix[i] = new char [m];
    
    int x1 = n, x2 = -1, y1 = -1, y2 = -1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j){
            std::cin >> matrix[i][j];
            if (matrix[i][j] == '*'){
                if (y1 == -1)
                    y1 = i;
                else
                    y2 = i;
            if (j < x1)
                x1 = j;
            if (j > x2)
                x2 = j;
            }
        }
    
    
    for (int i = y1; i < y1 + 3; ++i)
        for (int j = x1; j < x1 + 3; ++j){
            bool have_whole_cell = false;
            if (abs(i - j) != abs(x2 - y2)) //отсечение неквадратов
                continue;
            for (int x = j; x < x2 - 1; ++x)
                for (int y = i; y < y2 - 1; ++y)
                    if (matrix[y][x] == '.')
                        have_whole_cell = true;
            if (!have_whole_cell){
                std::cout << "SQUARE\n";
                goto del;
            }
        }
    std::cout << "CIRCLE\n";                
    del:
    for (int i = 0; i < n; ++i)
        delete[] matrix[i];
    delete[] matrix;
    
    return 0;
}
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 18:50     [Матрица] Круг или квадрат? #18
Цитата Сообщение от diagon Посмотреть сообщение
Т.к. проверка на дырки не идет по последним двум сторонам, то оба алгоритма считают это квадратом. Собственно, про это и был мой вопрос...
Если K равно 3, то все ячейки должны быть заполнены для квадрата. Просто дополни условие.
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 19:00  [ТС]     [Матрица] Круг или квадрат? #19
Цитата Сообщение от Deviaphan Посмотреть сообщение
Если K равно 3, то все ячейки должны быть заполнены для квадрата.
А если 3x4/4x3/4x4/etc ? Для всех случаев дополнительное условие писать?
P.S. исправил мелкую опечатку в коде, теперь Wrong Answer уже на 5 тесте(был на 6м) xD
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2011, 19:03     [Матрица] Круг или квадрат?
Еще ссылки по теме:

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

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

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

Принадлежит ли круг целому кругу или наоборот - C++
Проверить принадлежит ли кругцелому кругуили наоборот. По принципу истина и ложь Добавлено через 22 часа 26 минут Я уже 2 день её...

Проверить, принадлежит ли первой круг полностью другому кругу или наоборот - C++
Проверить, принадлежит ли круг(x-a1)2+(y-b1)2=R12 полностью кругу (x-a2)2+(y-b2)2=R22 или наоборот


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

Или воспользуйтесь поиском по форуму:
grizlik78
Эксперт С++
1904 / 1436 / 109
Регистрация: 29.05.2011
Сообщений: 2,990
30.07.2011, 19:03     [Матрица] Круг или квадрат? #20
Цитата Сообщение от diagon Посмотреть сообщение
Допустим, будет такой тест:
***
*.*
***
Квадратом это не могло являться только из-за ограниченности поля и размера квадрата. Для большего поля, с достаточным количеством свободного пространства вокруг, такую фигуру вполне можно получить из квадрата 3x3.
К счастью, такого теста там нет (либо ответ SQUARE для него считается правильным, что, конечно, не верно). Обработка граничных условий сильно бы осложнила алгоритм.
Yandex
Объявления
30.07.2011, 19:03     [Матрица] Круг или квадрат?
Ответ Создать тему
Опции темы

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