Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.56/34: Рейтинг темы: голосов - 34, средняя оценка - 4.56
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2

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

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

Студворк — интернет-сервис помощи студентам
Доброго времени суток.
Условие тут.
Просьба подсказать алгоритм или выложить код с кратким описанием идеи решения.
Сам довольно много думал, но ничего дельного не надумал... А задача должна быть несложной.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
29.07.2011, 20:54
Ответы с готовыми решениями:

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

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

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

36
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 19:07  [ТС]
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от grizlik78 Посмотреть сообщение
Для большего поля, с достаточным количеством свободного пространства вокруг, такую фигуру вполне можно получить из квадрата 3x3.
Каким образом?
Допустим, такой тест
..........
..........
..........
..........
..***.....
..*.*.....
..***.....
..........
..........
..........
Это ведь не может быть квадратом...
Ну а кроме таких случаев у меня вроде все предусмотрено.
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
30.07.2011, 19:09
Единички, это то, что было стёрто, двойки, это то, что было нарисовано:
..........
..........
..........
.111......
.1**2.....
.1*12.....
..222.....
..........
..........
..........
1
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 19:17
Цитата Сообщение от diagon Посмотреть сообщение
Для всех случаев дополнительное условие писать?
Это касается только размера с одной или обеими сторонами равным 3. Если размер N-2 меньше 2 (я предполагаю, что наименьший квадрат имеет размер 2х2), то просто отсекаешь по краям не по 2, а поменьше строчек/столбцов. Т.е. лишь слегка усложняется алгоритм определения внутренней подматрицы.
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 19:18  [ТС]
grizlik78, Но по вашему алгоритму так немного не получиться..
Ведь здесь вообще нельзя построить квадраты, которые были бы минимум на 2 клетки удалены от всех сторон квадрата. Для этого нужна область минимум 4х4, и все случаи рассматривать как-то нерационально.
Deviaphan, спасибо, попробую...
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
30.07.2011, 19:24
diagon, в каком смысле не получится? Достаточно чтобы хоть один квадрат был не дальше 2 клеток всего от 2 сторон: правой и нижней. Здесь же таких квадратов целых 8, все из одной клетки состоящие.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
/tmp $ g++ sqrcirc.cpp && cat input.txt && ./a.out && cat output.txt 
10 10
..........
..........
..........
..........
..***.....
..*.*.....
..***.....
..........
..........
..........
SQUARE
1
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2011, 19:35  [ТС]
Как квадрат из одной клетки состоять может? о_О
Если из четырех, то точка мешает такие квадраты сделать.
Но вообще таких тестов видимо нету, а я немного не так алгоритм понял(непонятно, на чем основывается такое решение), сейчас переделаю...
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
30.07.2011, 19:36
Цитата Сообщение от diagon Посмотреть сообщение
Как квадрат из одной клетки состоять может? о_О
ну клетка-то квадратная
1
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
30.07.2011, 19:37
Цитата Сообщение от grizlik78 Посмотреть сообщение
ну клетка-то квадратная
Символ "*" больше напоминает круг.)))
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
30.07.2011, 19:39
Цитата Сообщение от Deviaphan Посмотреть сообщение
Символ "*" больше напоминает круг.)))
Снежинку овальную. Но в задаче картинка с квадратными клетками а звёздочки и точки лишь для отличия закрашенных от незакрашенных.
0
30.07.2011, 19:41

Не по теме:

Холивар 2011!
Точка - КРУГ она или КВАРДАТ?

0
30.07.2011, 19:44

Не по теме:

Точка — круг, но круг — квадрат. Мне заказ, тебе откат! (Все герои вымышленны, все совпадения случайны)

1
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
31.07.2011, 13:21  [ТС]
Блин, эта задача меня убивает...
Вроде как реализовал этот алгоритм.
Цитата Сообщение от 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
#include <iostream>
#define DEBUG
int main(){
    #ifndef DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    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;
    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 y = y1; y < y1 + 3; ++y)
        for (int x = x1; x < x1 + 3; ++x)
        {
            bool have_empty_cell = false;
            for (int _x = x, _y = y; 
            !have_empty_cell && _x < x2 && _y < y2;
            ++_x, ++_y)
            {   
                int i, j;
                for (i = y; i <= _y; ++i)
                {
                    for (j = x; j <= _x; ++j)
                        if (matrix[i][j] == '.')
                        {   
                            have_empty_cell = true;
                            if (i != _y && j != x)
                            {
                                --_y;
                                --_x;
                            }
                            break;
                        }
                        if (have_empty_cell)
                            break;
                }
                
                if ( (i != _y || j != _x || !have_empty_cell) && x2 - _x <= 2 && y2 - _y <= 2   )
                            {
                                #ifdef DEBUG
                                std::cout
                                        << std::endl
                                        << x << ' ' << y
                                        << std::endl
                                        << _x << ' ' << _y
                                        << std::endl
                                        << i << ' ' << j 
                                        << std::endl
                                        << std::boolalpha << have_empty_cell
                                        << std::endl;
                                #endif
                                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;
}

Но опять же получаю Wrong Answer на 5 тесте.
И все равно мне непонятно, как этот алгоритм работает.
На чем он вообще основывается?
Еще вот такой тест придумал
Code
1
2
3
4
5
6
7
8
9
10
....*.....
.....*....
...****...
...***....
...****...
...****...
..........
..........
..........
..........
Нету здесь квадрата.
Однако из точки (4,3) (нумерация с единицы) можно провести недырявый квадрат в точку (6, 5).
Если бы не закрашенная точку сверху, то он мог бы существовать. Но он не существует, а ваш алгоритм говорит об обратном.
Хотя может тут не в алгоритме дело, это уже 3 алгоритм, который на 5 тесте валиться >_>
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
31.07.2011, 13:58
Цитата Сообщение от diagon Посмотреть сообщение
Нету здесь квадрата.
Да есть, есть.
10 10
....2.....
..111*1...
..1****...
..1***1...
..1****...
..1****...
..........
..........
..........
..........

Цитата Сообщение от diagon Посмотреть сообщение
Хотя может тут не в алгоритме дело, это уже 3 алгоритм, который на 5 тесте валиться >_>
В верхней строчке результатов моя реализация моего алгоритма Может я его неправильно реализовал просто?

Добавлено через 23 минуты
diagon, для картинки с одной единственной звёздочкой твоя реализация получает неправильное значение для y2 и выдаёт CIRCLE, хотя одна звёздочка вполне могла остаться от квадрата 3x3
1
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
31.07.2011, 14:04  [ТС]
Цитата Сообщение от grizlik78 Посмотреть сообщение
diagon, для картинки с одной единственной звёздочкой твоя реализация получает неправильное значение для y2 и выдаёт CIRCLE, хотя одна звёздочка вполне могла остаться от квадрата 3x3
Убрал там else, все равно WA5 =(
А в какой строке else надо убрать?
В 30й
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
31.07.2011, 14:18
Ну, я только ещё собираюсь разобраться с реализацией. А в какой строке else надо убрать?

Добавлено через 11 минут
В строке 44 должны быть <= вместо меньше, как мне кажется. По-крайней мере для одноклеточной — точно.
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
31.07.2011, 14:21  [ТС]
Цитата Сообщение от grizlik78 Посмотреть сообщение
строке 44 должны быть <= вместо меньше, как мне кажется. По-крайней мере для одноклеточной — точно.
Accepted
Всем спасибо!
P.S. над кодом издеваться все же не буду ибо лень и не умею нормальные макросы для циклов писать.
0
Эксперт С++
 Аватар для grizlik78
2383 / 1667 / 279
Регистрация: 29.05.2011
Сообщений: 3,402
31.07.2011, 14:26
Цитата Сообщение от diagon Посмотреть сообщение
И все равно мне непонятно, как этот алгоритм работает.
На чем он вообще основывается?
Алгоритм основан на медитации вот над этой картинкой:
Название: image.asp.gif
Просмотров: 13

Размер: 3.7 Кб
После изменений клетки с цифрами могут стать какими угодно, неизменным остаётся только внутренний квадрат. Задача — найти его, если он есть. Вокруг этого квадрата 2 клетки неопределённости.
Первоначальный выбор 9 точек обусловлен тем, что после изменений координаты x1 и y1 могут отстоять от угла искомого квадрата на 0, 1 и 2 клетки. Ну а расширяя квадрат по диагонали вниз и вправо мы обязательно захватим искомый квадрат хотя бы из одной из 9 начальных клеток (ну может и 1-2 лишних линии).
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
31.07.2011, 14:26

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
37
Ответ Создать тему
Новые блоги и статьи
Доктрина интенционального знания - Доктрина для портала "Срез".
Hrethgir 25.07.2026
Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .
сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых
anaschu 25.07.2026
Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.
сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил
anaschu 25.07.2026
две стороны одной монеты
Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад).
Hrethgir 24.07.2026
В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .
Вот представьте что вам дали бессмертие.
kumehtar 24.07.2026
Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .
сукцессия 41
anaschu 24.07.2026
Численная верификация бифуркации в агентной модели лесной сукцессии: от одного параметра к ансамблю Автор: пользователь @Shumilov_AS | Раздел: Прикладная математика / Численные методы Кратко. . .
сукцессия 40. Ансамблевая кластерная параметризаци, часть 1.
anaschu 24.07.2026
Пр# Сопровождение научной статьи ИИ-ассистентом: подготовка публикации и калибровка агентно-ориентированной модели сукцессии микоризных систем **Полевые заметки о двухнедельной совместной работе**. . .
Теория всего 12. ВГК на планете в стратегической игре "терра"
anaschu 21.07.2026
### Главные семантические изменения и дешифровка новой физики 1. **`REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`)**: Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru