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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Считывание данных из файла с 4мя столбцами http://www.cyberforum.ru/cpp-beginners/thread822855.html
Необходимо считать данные в 4 переменные из 4х разных столбцов, сам файл весит 10мб. То есть файл огромный, но в нём данные располагаются строго в 4х столбцах, разделенные между собой пробелом....
C++ Лабы по СМО Доброго времени суток! кто сможет помочь с выполнением 3-х лабораторных работ на С++? сроки до завтра. Запрещено создавать темы с множеством вопросов во всех разделах, кроме разделов платных... http://www.cyberforum.ru/cpp-beginners/thread822850.html
Что будет если так сделать? C++
Всем привет! Что будет если применить такую конструкцию int global; void Test(const int& a) { global = a; } То переменная a СКОПИРУЕТСЯ в переменную global?
Выполнение программы простой структуры. Вычисление выражений с использованием стандартных функций C++
Доброго времени суток! я прошу вас о помощи программисты! первая задача: 1.Для задачи 1 определить тип заданных выражений и найти их значения. Составить систему тестов и вычислить полученное...
C++ Обращение к вектору полученному через указатель http://www.cyberforum.ru/cpp-beginners/thread822830.html
Всем привет, Появился вопрос по поводу обращения к вектору полученному через указатель. Выглядит так: Передаю адрес вектора в указатель: std::vector<short> *getData(){return &sampleData;} ...
C++ просумировать чётные элементы целочисленного массива просумировать чётные элементы целочисленного массива Добавлено через 11 минут плиииз)) не хочется на пересдачу приходить((( подробнее

Показать сообщение отдельно
Wanee
54 / 54 / 13
Регистрация: 02.02.2011
Сообщений: 434

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

30.03.2013, 13:29. Просмотров 573. Ответов 8
Метки (Все метки)

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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru