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


Город представлен на матрицу м х N, где строки нумеруются от 1 до п, а столбцы нумеруются от 1 до метров.

Трамваи всегда идут прямо вдоль ряда. Начальной точкой дороги является (Р, С1) и конечная точка (Р, С2), где Р - число строк, С1 - начальный столбец и С2 - конец столбца.

Нам необходимо определить количество ячеек, не занимают трамвайные пути. Внимание: трамвайные пути могут пересекаться в одной строке.

Формат ввода: первая строка содержит 3 целочисленные значения: П - количество строк, м -количество столбцов, к - количество трамваев. В каждой следующей строке я от общего к линии содержит 3 целых значения: Р, С1, С2.

Формат выходных данных: целое число, представляющее количество клеток, не занимают трамвайные пути.

Ограничения:

1 <= Н, М <= 10^9

0 <= К <= 1000

1 <= Р <= Н

1 <= С1, С2 <= М

Язык: C или C++

Решение:

#include <fstream>

template <class T> struct Node
{
    T value;
    Node *left;     // less
    Node *right;    // more
    bool flag;

    Node(T value) : value(value), left(0), right(0), flag(false)
    {
    }

    virtual ~Node()
    {
    }
};

template <class T> class BST
{
protected:
    Node<T> *root;

    virtual Node<T>* constructHelper(T value)
    {
        return new Node<T>(value);
    }

    Node<T>* getHelper(Node<T> **p, T value)
    {
        Node<T> *node, *root, *arr[3];

        root = *p;

        if (root->value > value)
        {
            if (!root->left)
            {
                node = root->left = constructHelper(value);

                if (!root->right) root->flag = true;
            }
            else
            {
                node = getHelper(&root->left, value);

                if (root->flag)
                {
                    if (root->left->left)
                    {
                        arr[2] = root->left->left;
                        root->left->left = 0;

                            arr[1] = root->left;
                            root->left->flag = false;
                            root->left = 0;
                            arr[0] = root;
                            root->flag = false;

                        root = arr[1];
                        root->left = arr[2];
                        root->right = arr[0];

                        *p = root;
                    }
                    else if (root->left->right)
                    {
                        arr[2] = root->left->right;
                        root->left->right = 0;

                            arr[1] = root->left;
                            root->left->flag = false;
                            root->left = 0;
                            arr[0] = root;
                            root->flag = false;

                        root = arr[2];
                        root->left = arr[1];
                        root->right = arr[0];

                        *p = root;
                    }
                }
            }
        }
        else if (root->value < value)
        {
            if (!root->right)
            {
                node = root->right = constructHelper(value);

                if (!root->left) root->flag = true;
            }
            else
            {
                node = getHelper(&root->right, value);

                if (root->flag)
                {
                    if (root->right->right)
                    {
                        arr[2] = root->right->right;
                        root->right->right = 0;

                            arr[1] = root->right;
                            root->right->flag = false;
                            root->right = 0;
                            arr[0] = root;
                            root->flag = false;

                        root = arr[1];
                        root->left = arr[0];
                        root->right = arr[2];

                        *p = root;
                    }
                    else if (root->right->left)
                    {
                        arr[2] = root->right->left;
                        root->right->left = 0;

                            arr[1] = root->right;
                            root->right->flag = false;
                            root->right = 0;
                            arr[0] = root;
                            root->flag = false;

                        root = arr[2];
                        root->left = arr[0];
                        root->right = arr[1];

                        *p = root;
                    }
                }
            }
        }
        else node = root;

        return node;
    }

    void removeHelper(Node<T> *root)
    {
        if (root->left) removeHelper(root->left);

        if (root->right) removeHelper(root->right);

        delete root;
    }

public:

    Node<T>* getNode(T value)
    {
        Node<T> *node;

        if (!root)
        {
            root = constructHelper(value);
            node = root;
        }
        else
        {
            node = getHelper(&root, value);
        }

        return node;
    }

    BST() : root(0)
    {
    }

    ~BST()
    {
        if (root) removeHelper(root);
    }
};

//......................................................................................................................

template <class T, unsigned long long columns_width> class ColumnBST;

template <class T, unsigned long long raws_width, unsigned long long columns_width> struct RawNode : public Node<T>
{
    ColumnBST<T, columns_width> *raws[raws_width];

    RawNode(T value) : Node(value)
    {
        for (T i = 0; i < raws_width; ++i) raws[i] = 0;
    }

    virtual ~RawNode()
    {
        for (T i = 0; i < raws_width; ++i) if (raws[i]) delete raws[i];
    }
};

template <class T, unsigned long long raws_width, unsigned long long columns_width> class RawBST : public BST<T>
{
    virtual Node<T>* constructHelper(T value)
    {
        return new RawNode<T, raws_width, columns_width>(value);
    }

public:

    ColumnBST<T, columns_width>* getRaw(T r)
    {
        T x, y;
        RawNode<T, raws_width, columns_width> *node;

        --r;

        x = r / raws_width;
        y = r % raws_width;

        node = (RawNode<T, raws_width, columns_width>*)getNode(x);

        if (!node->raws[y]) node->raws[y] = new ColumnBST<T, columns_width>();

        return node->raws[y];
    }
};

//......................................................................................................................

template <class T, unsigned long long columns_width> class RailList;

template <class T, unsigned long long columns_width> struct ColumnNode : public Node<T>
{
    RailList<T, columns_width> *rails;

    ColumnNode(T value) : Node(value), rails(0)
    {
    }

    virtual ~ColumnNode()
    {
        if (rails) delete rails;
    }
};

template <class T, unsigned long long columns_width> class ColumnBST : public BST<T>
{
    virtual Node<T>* constructHelper(T value)
    {
        return new ColumnNode<T, columns_width>(value);
    }

public:

    T addRail(T c1, T c2)
    {
        T a, b, value;
        ColumnNode<T, columns_width> *node;

        --c1;
        --c2;

        a = c1 / columns_width;
        b = c2 / columns_width;

        if (a == b)
        {
            node = (ColumnNode<T, columns_width>*)getNode(a);
            if (!node->rails) node->rails = new RailList<T, columns_width>();

            value = node->rails->addRail(c1 % columns_width, c2 % columns_width);
        }
        else
        {
            node = (ColumnNode<T, columns_width>*)getNode(a);
            if (!node->rails) node->rails = new RailList<T, columns_width>();

            value = node->rails->addRail(c1 % columns_width, columns_width - 1);
            ++a;

            while (a < b)
            {
                node = (ColumnNode<T, columns_width>*)getNode(a);
                if (!node->rails) node->rails = new RailList<T, columns_width>();

                value += node->rails->addRail(0, columns_width - 1);
                ++a;
            }

            node = (ColumnNode<T, columns_width>*)getNode(a);
            if (!node->rails) node->rails = new RailList<T, columns_width>();

            value += node->rails->addRail(0, c2 % columns_width);
        }

        return value;
    }
};

//......................................................................................................................

template <class T> struct RailNode
{
    RailNode *next;
    T c1, c2;

    RailNode(T c1, T c2) : next(0), c1(c1), c2(c2)
    {
    }
};

template <class T, unsigned long long columns_width> class RailList
{
    RailNode<T> *rail;
    T total, min, max;

    T addRailHelper2(RailNode<T> *rail, T c1, T c2)
    {
        T value;

        if (!rail->next)
        {
            rail->next = new RailNode<T>(c1, c2);

            value = (c2 - c1) + 1;
        }
        else
        {
            value = addRailHelper(rail->next, c1, c2);
        }

        return value;
    }

    T addRailHelper(RailNode<T> *rail, T c1, T c2)
    {
        T value;

        if ((c1 > rail->c2) || (c2 < rail->c1))
        {
            value = addRailHelper2(rail, c1, c2);
        }
        else if ((c1 < rail->c1) || (c2 > rail->c2))
        {
            value = 0;

            if (c1 < rail->c1)
            {
                value += addRailHelper2(rail, c1, rail->c1 - 1);
            }

            if (c2 > rail->c2)
            {
                value += addRailHelper2(rail, rail->c2 + 1, c2);
            }
        }
        else value = 0;

        return value;
    }

    void removeRailHelper(RailNode<T> *rail)
    {
        RailNode<T> *node;

        while (rail)
        {
            node = rail->next;
            delete rail;
            rail = node;
        }
    }

public:

    RailList() : rail(0), total(0), min(0), max(0)
    {
    }

    ~RailList()
    {
        if (rail) removeRailHelper(rail);
    }

    T addRail(T c1, T c2)
    {
        T value;
        RailNode<T> *next, *node;

        if (!rail)
        {
            rail = new RailNode<T>(c1, c2);

            value = (c2 - c1) + 1;

            min = c1;
            max = c2;

            total = value;
        }
        else
        {
            if (total != columns_width)
            {
                if ((c1 > max) || (c2 < min))
                {
                    node = new RailNode<T>(c1, c2);

                    next = rail->next;
                    rail->next = node;
                    node->next = next;

                    value = (c2 - c1) + 1;
                }
                else
                {
                    value = addRailHelper(rail, c1, c2);
                }

                if (c1 < min) min = c1;
                if (c2 > max) max = c2;

                total += value;
            }
            else value = 0;
        }

        return value;
    }
};

//......................................................................................................................

template <class T, unsigned long long raws_width, unsigned long long columns_width> class City
{
    T n, m, k, i, count;
    RawBST<T, raws_width, columns_width> *raws;

public:

    City(T n, T m, T k) : i(0), count(0), raws(0)
    {
        if (((n >= 1) && (n <= 1000000000)) && ((m >= 1) && (m <= 1000000000)) && (k <= 1000))
        {
            this->n = n;
            this->m = m;
            this->k = k;
        }
        else throw std::out_of_range("");
    }

    ~City()
    {
        if (raws) delete raws;
    }

    T getResult()
    {
        return ((n * m) - count);
    }

    void addRail(T r, T c1, T c2)
    {
        ColumnBST<T, columns_width> *raw;

        if (((i < k) && (r >= 1) && (r <= n)) && ((c1 >= 1) && (c1 <= m)) && ((c2 >= 1) && (c2 <= m) && (c2 >= c1)))
        {
            if (!raws) raws = new RawBST<T, raws_width, columns_width>();

            raw = raws->getRaw(r);

            count += raw->addRail(c1, c2);

            ++i;
        }
        else throw std::out_of_range("");
    }
};

//......................................................................................................................

int main(int argc, char* argv[])
{
    std::fstream input_file("input.txt", std::ios_base::in);

    unsigned long long n, m, k;

    input_file >> n;
    input_file >> m;
    input_file >> k;

    City<unsigned long long, 32, 10000000> *city = new City<unsigned long long, 32, 10000000>(n, m, k);

    unsigned long long r, c1, c2;

    for (unsigned long long i = 0; i < k; ++i)
    {
        input_file >> r;
        input_file >> c1;
        input_file >> c2;

        city->addRail(r, c1, c2);
    }

    unsigned long long result = city->getResult();

    delete city;

    std::fstream output_file("output.txt", std::ios_base::out);

    output_file << result;

    return 0;
}

И она была отклонена работодателем (Стажер с позиции разработчика++). Можете ли вы помочь разобраться, действительно ли это страшно или нет? Я никогда не был заинтересован в алгоритмах и я упал, как я с кодером, который бросает все абстракции подальше. Спасибо.



146
1
задан 13 апреля 2018 в 02:04 Источник Поделиться
Комментарии
1 ответ

Это выглядит как очень сложный и память-голодный решение. С ВСЕ эти сложности, я ожидал увидеть несколько модульных тестов в обзоре, но их нет.

Я ожидал увидеть решение, которое считывает все входные данные, группируя их по строкам (например, в std::multimap), а затем выполняет итерации по строкам, комбинируя пересекающиеся рельсы, чтобы получить общее для этой строки.

Существует ряд ошибок при компиляции с новым стандартом:


  • Node в качестве базового класса, имя должно быть Node<T> (в инициализаторы RawNode и RawBST)

  • деклараций в зависимые базы BST<long long unsigned int> не нашли неквалифицированным поиска, поэтому нужно писать this->getNode(a) вместо того, чтобы просто getNode(a) в кучу мест.

Даже с учетом ошибки исправлены, есть почти сто строк предупреждений, когда я компиляции с g++ -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Weffc++. Я рекомендую играть на них.

3
ответ дан 19 апреля 2018 в 02:04 Источник Поделиться