Задача "Цветная бумага"

@Wanee · Регистрация: 02.02.2011

Студворк — интернет-сервис помощи студентам

N прямоугольников (1 ≤ N ≤ 1000) из цветной бумаги положили на лист белой бумаги шириной A и длиной B. Стороны прямоугольников параллельны сторонам листа. Все прямоугольники находятся в пределах границы листа и образуют фигуры разных цветов, если взглянуть сверху.
Начало системы координат (0, 0) совпадает с нижним левым углом листа белой бумаги, оси направлены по его сторонам.
Исходные данные
Порядок на вводе совпадает с тем, в котором положили на лист прямоугольники. Первая строка соответствует прямоугольнику «на дне». Первая строка содержит числа A, B и N через пробел (1 ≤ A, B ≤ 10000). Строки 2, …, N + 1 содержат по пять целых чисел: llx, lly, urx, ury, color: координаты нижнего левого и верхнего правого углов прямоугольника цвета color (1 ≤ color ≤ 2500). Белый лист имеет цвет 1.
Результат
Выведите список всех цветов, которые видны сверху, вместе с общей видимой площадью каждого цвета. Список должен быть упорядочен по цвету. Не нужно выводить цвета с нулевой видимой площадью.

исходные данные
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4
результат
1 91
2 84
3 187
4 38

Я пытался взять поле A на B и отмечать на нем прямоугольники цветами, а потом подсчитывал количество клеток. Но для больших полей все будет просчитываться очень долго. Помогите реализовать более быстрый алгоритм.

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
#include <fstream>
 
using namespace std;
 
struct Rec{
    signed short col;
    long area;
}; 
 
int main(){
    ifstream in("input.txt");
    ofstream out("output.txt");
    
    signed short a, b, n, llx, lly, urx, ury, col;
    signed short **from;
    Rec *arr;
 
    in >> a >> b >> n;
 
    from = new signed short*[a];
    for(register signed short j = 0; j < a; j++){
        from[j] = new signed short[b];
        for(register signed short i = 0; i < b; i++) from[j][i] = 1;
    }
 
    arr = new Rec[n + 1];
 
    arr[0].area = 0;
    arr[0].col = 1;
    for(register signed short q = 1; q < n + 1; q++){
        arr[q].area = 0;
        in >> llx >> lly >> urx >> ury >> col;
        arr[q].col = col;
        for(register signed short j = lly; j < ury; j++)
            for(register signed short i = llx; i < urx; i++) from[j][i] = col;
    }
 
    for(register signed short j = 0; j < a; j++)
        for(register signed short i = 0; i < b; i++)
            for(register signed short q = 0; q < n + 1; q++)
                if(from[j][i] == arr[q].col){
                    arr[q].area++;
                    break;
                }
 
    for(register signed short q = 0; q < n + 1; q++){
        out << arr[q].col << ' ' << arr[q].area;
        if(q != n) out << '\n';
    }
 
    delete []arr;
 
    for(register signed short j = 0; j < b; j++) delete []from[j];
    delete []from;
 
    in.close();
    out.close();
 
    return 0;
}

@gazlan · 30.03.2013, 18:50

Прежде всего сведите хадачу к однородной, считая что "дно" само лежит на бесконечной плоскости нулевого цвета и может накрыто или НЕ накрыто верхним прямоугольником.

Далее, если представить, что цветных слоев всего два, то верхний слой виден целиком, а из площади нижнего цвета вычитается площадь перекрывающего его верхнего цвета.

А теперь делаете все это рекурсивно: из самого верхнего слоя ничего не вычитается, из следующего - область перекрытия его верхним, из третьего - область перекрытия его вторым + то, что от первого выходит за рамки второго итд.

@salam · 30.03.2013, 20:15

кажется, что если посортить все запросы по координатам, сохранив порядок следования, и считать ответ для каждого запроса в отдельности, то можно за O(n*logn) все сделать.

Добавлено через 1 минуту
то есть у вас есть запрос llx, lly, urx, ury. если он не пересечется, то для него ответ просто площадь прямоугольника, если пересечется - вычесть кусочек. общий ответ как сумма ответов по запросам.

@Wanee · 01.04.2013, 09:29 **[ТС]**

salam, не могли бы помочь с алгоритмом, а то я вас не совсем понял.

@alexcrz · 01.04.2013, 10:09

прямоугольники могут и не перекрывать друг друга - рекурсия тут частный случай.
предлагаю в двумерный массив загнать номера цветов и с этим работать - тем более, что просят результать отсортировать по цветам и количеству занятых ячеек массива/площади.

@Wanee · 01.04.2013, 14:36 **[ТС]**

alexcrz, я так и сделал, загнал все в двумерный массив, но это работает медленно для больших чисел...

@salam · 01.04.2013, 15:56

у вас как отношения с STL?

@alexcrz · 01.04.2013, 19:32

Как отсортировать вектор векторов и найти повторы буду изучать завтра - по картинке результат вроде похож на правду

Еще дурная мысль - запомнить цвета и искать их количество в векторе, а не все 2500. Тогда сортировка не нужна - просто перебрать. Хотя при большом количестве наложений и малой площади лучше все же сортировка.

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
#include <iostream>
#include <vector>
using namespace std;
 
 
int main()
{
    int xtotal = 20, ytotal = 20, q=3;
    vector<int> x(xtotal, 1);
    vector<vector<int>> y(ytotal, x);
    int x1, y1, x2, y2, color;
    cout << "Enter x1, y1, x2, y2 and color" << endl;
    do
    {
        cin >> x1 >> y1 >> x2 >> y2 >> color;  
        for (int i=x1; i < x2; i++)
            for (int j=y1; j < y2; j++)
                y[i][j] = color;
        q--;
    }
    while (q > 0);
for (int i=19; i > 0; i--)
    { cout << endl;
        for (int j=0; j < 20; j++)  
                cout << y[j][i];
    }
    cout << endl;
    system ("pause");
}

Добавлено через 10 минут
в 22 строке i >= 0
= потерял

@alexcrz · 04.04.2013, 15:48

Если целиком, то как-то так... была мысль начинать искать следующий цвет после непрерывного повторения предыдущего... не получилость

1111111111111111111
111112222222222..

то есть начинать со второго ряда, с середины.

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
#include <iostream>
#include <vector>
using namespace std;
 
 
int main()
{
    int xtotal = 20, ytotal = 20, q=3;
    vector<int> x(xtotal, 1);
    vector<vector<int>> y(ytotal, x);
    int x1, y1, x2, y2, color;
    cout << "Enter x1, y1, x2, y2 and color" << endl;
    do
    {
        cin >> x1 >> y1 >> x2 >> y2 >> color;  
        for (int i=x1; i < x2; i++)
            for (int j=y1; j < y2; j++)
                y[i][j] = color;
        q--;
    }
    while (q > 0);
for (int i=19; i >= 0; i--)
    { cout << endl;
        for (int j=0; j < 20; j++)  
                cout << y[j][i];
    }
    cout << endl << endl;
    
 
    int count = 0, color_chk = -1;
 
    for (int t1 = 0; t1 < xtotal; t1++)
        for (int t2 = 0; t2 < ytotal; t2++)
        {  
            if (y[t1][t2] != -1) 
            {
                color_chk = y[t1][t2];
                count = 0;
 
                for (int i = 0; i < xtotal; i++)
                for (int j = 0; j < ytotal; j++)
                    if (color_chk == y[i][j])
                    {
                        count++;
                        y[i][j] = -1;
                    }
 
                cout << color_chk << " " << count << endl;
            } 
        }
    
system ("pause");
}

Добавлено через 1 час 27 минут
Wanee. решил ваш код изучит (до этого не смотрел). Я так понял, что цвета отдельно в массиве и его надо еще очистить от дублей?

Подал на вход

20 20 3
2 2 18 18 2
0 8 19 19 2
8 0 10 19 4

получил

1 91
2 271
2 0
4 38

Вопрос.
Как начать просматривать двумерный массив с конкретного места array[x][y], где x и y при первом заходе на просмотр равны нулям, а при последующих - изменяются по результату просмотра.

Если конкретно по задаче. Я просмотрел 578 рядов по 10000 цветов в каждом. Так как я перебираю цвета по порядку - в этих рядах ничего интересного для меня нет. В коде я заменил их содержимое на -1. Но зачем мне сравнивать эти 5780000 "минус единиц" с еще не просеянным цветом в следующей 579-й строке?

Добавлено через 1 час 42 минуты
Разобрался вроде сам. Количество операций при сверке конкретного цвета со всем массивом уменьшилось с 400 до 80 при данном вводе значений. Помогло ли это сократить время выполнения на больших объемах?

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
#include <iostream>
#include <vector>
using namespace std;
 
 
int main()
{
    int xtotal = 20, ytotal = 20, q=3;
    vector<int> x(xtotal, 1);
    vector<vector<int>> y(ytotal, x);
    int x1, y1, x2, y2, color;
    cout << "Enter x1, y1, x2, y2 and color" << endl;
    do
    {
        cin >> x1 >> y1 >> x2 >> y2 >> color;  
        for (int i=x1; i < x2; i++)
            for (int j=y1; j < y2; j++)
                y[i][j] = color;
        q--;
    }
    while (q > 0);
for (int i=19; i >= 0; i--)
    { cout << endl;
        for (int j=0; j < 20; j++)  
                cout << y[j][i];
    }
    cout << endl << endl;
    
 
    int count = 0, color_chk = -1, cycle = 0, ichk = 0, jchk = 0, xchk = 0, ychk = 0, end = 0;
 
    for (int t1 = 0; t1 < xtotal; t1++)
        for (int t2 = 0; t2 < ytotal; t2++)
        {  
            if (y[t1][t2] != -1) 
            {
                color_chk = y[t1][t2];
                count = 0;
                xchk = ichk;
                ychk = jchk;
                end = 0;
 
                for (int i = 0; i < xtotal; i++)
                {cycle++;
                        if (xchk > 0) {i = xchk; xchk = -1;} 
                        for (int j = 0; j < ytotal; j++)
                        {
                            if (ychk > 0) {j = ychk; ychk = -1;}
                            if (color_chk == y[i][j])
                            {
                                
                                count++;
                                if (end ==0) {ychk++;
                                if (ychk == ytotal) {jchk = 0; ychk++;}}
                                y[i][j] = -1;
                            } else end = -1;
                        }
                }
 
                cout << color_chk << " " << count << endl;
            } 
        }
    cout << "total operations: " << cycle << endl;
system ("pause");
}

Добавлено через 1 час 1 минуту
9 и 10 строку надо изменить, перепутал x c y... иначе возможен выход за пределы вектора

C++
1
2
vector<int> x(ytotal, 1);
    vector<vector<int>> y(xtotal, x);

в 22-25 заменить цифры на константы, если нужена демонстрация и хотите изменить размер нижнего основного листа

C++
1
2
3
4
for (int i=(xtotal-1); i >= 0; i--)
    { cout << endl;
        for (int j=0; j < ytotal; j++)  
                cout << y[j][i];

Добавлено через 21 час 32 минуты
Добавил определение позиции очередного цвета в циклах t1 и t2.
Исправил "начальную позицию" с которой он будет сравниваться в циклах i и j.
Данные читаются и записываются в файлы input.txt и output.txt

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
#include <iostream>
#include <vector>
#include <fstream>
#include <stdlib.h>
using namespace std;
 
 
int main()
{ 
// Заполнение вектора ----------------------------------------------------------------
 
    int xtotal = 0, ytotal = 0, q=0;
    
    int x1, y1, x2, y2, color;
    ifstream in("input.txt");
    ofstream out("output.txt");
    in >> xtotal >> ytotal >> q;
    vector<int> x(ytotal, 1);
    vector<vector<int>> y(xtotal, x);
    do
    {
        in >> x1 >> y1 >> x2 >> y2 >> color;  
        for (int i=x1; i < x2; i++)
            for (int j=y1; j < y2; j++)
                y[i][j] = color;
        q--;
    }
    while (q > 0);
 
// Вывод на экран. При больших xtotal и ytotal может не влезть  
 
    for (int j=(ytotal - 1); j >= 0; j--)
    { 
        cout << endl;
        for (int i = 0; i < xtotal; i++)
            cout << y[i][j];
    }
    cout << endl << endl;
    
// Берем цвет по очереди и сравниваем со элементами вектора, которые идут после. Провереные цвета переименовываем в -1. 
 
    int count = 0, color_chk = -1, cycle = 0, ichk = 0, jchk = 0, xchk = 0, ychk = 0, end = 0;
 
    for (int t1 = 0; t1 < xtotal; t1++)
        for (int t2 = 0; t2 < ytotal; t2++)
        {  
            if (y[t1][t2] != -1) 
            {
                color_chk = y[t1][t2];
                count = 0;
                xchk = ichk;
                ychk = jchk;            
                end = 0;
 
                for (int i = 0; i < xtotal; i++)
                {
                        if (xchk > 0) {i = xchk; xchk = -1;} 
                        for (int j = 0; j < ytotal; j++)
                        {
                            if (ychk > 0) {j = ychk; ychk = -1;}
                            if (color_chk == y[i][j])
                            {
                                
                                count++;
                                if (end == 0) {jchk++;
                                if (jchk == ytotal) {jchk = 0; ichk++;}}
                                y[i][j] = -1;
                            } else end = -1;
                        }
                }
 
 
                out << color_chk << " " << count << endl;
                t1 = ichk;
                t2 = jchk;              
            } 
        }
    
    in.close();
    out.close();
    system("pause");
}

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	30.03.2013, 18:50
	Прежде всего сведите хадачу к однородной, считая что "дно" само лежит на бесконечной плоскости нулевого цвета и может накрыто или НЕ накрыто верхним прямоугольником. Далее, если представить, что цветных слоев всего два, то верхний слой виден целиком, а из площади нижнего цвета вычитается площадь перекрывающего его верхнего цвета. А теперь делаете все это рекурсивно: из самого верхнего слоя ничего не вычитается, из следующего - область перекрытия его верхним, из третьего - область перекрытия его вторым + то, что от первого выходит за рамки второго итд. 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	30.03.2013, 20:15
	кажется, что если посортить все запросы по координатам, сохранив порядок следования, и считать ответ для каждого запроса в отдельности, то можно за O(nlogn) все сделать. Добавлено через 1 минуту* то есть у вас есть запрос llx, lly, urx, ury. если он не пересечется, то для него ответ просто площадь прямоугольника, если пересечется - вычесть кусочек. общий ответ как сумма ответов по запросам. 0

@Wanee 54 / 54 / 23 Регистрация: 02.02.2011 Сообщений: 436
	01.04.2013, 09:29 [ТС]
	salam, не могли бы помочь с алгоритмом, а то я вас не совсем понял. 0

@alexcrz 13 / 16 / 5 Регистрация: 26.03.2013 Сообщений: 142
	01.04.2013, 10:09
	прямоугольники могут и не перекрывать друг друга - рекурсия тут частный случай. предлагаю в двумерный массив загнать номера цветов и с этим работать - тем более, что просят результать отсортировать по цветам и количеству занятых ячеек массива/площади. 0

@Wanee 54 / 54 / 23 Регистрация: 02.02.2011 Сообщений: 436
	01.04.2013, 14:36 [ТС]
	alexcrz, я так и сделал, загнал все в двумерный массив, но это работает медленно для больших чисел... 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	01.04.2013, 15:56
	у вас как отношения с STL? 0