---

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <windows.h>

// Структура для хранения пикселя (RGB)
struct Pixel {
    unsigned char r;
    unsigned char g;
    unsigned char b;

    Pixel() : r(0), g(0), b(0) {}
    Pixel(unsigned char red, unsigned char green, unsigned char blue)
        : r(red), g(green), b(blue) {}

    bool operator==(const Pixel& other) const {
        return (r == other.r) && (g == other.g) && (b == other.b);
    }

    bool operator!=(const Pixel& other) const {
        return !(*this == other);
    }
};

// Структура для RLE записи
struct RLERecord {
    Pixel color;
    int count;

    RLERecord() : count(0) {}
    RLERecord(const Pixel& p, int c) : color(p), count(c) {}
};

// Заголовки BMP файла
#pragma pack(push, 1)
struct BMPFileHeader {
    unsigned short bfType;
    unsigned int bfSize;
    unsigned short bfReserved1;
    unsigned short bfReserved2;
    unsigned int bfOffBits;
};

struct BMPInfoHeader {
    unsigned int biSize;
    int biWidth;
    int biHeight;
    unsigned short biPlanes;
    unsigned short biBitCount;
    unsigned int biCompression;
    unsigned int biSizeImage;
    int biXPelsPerMeter;
    int biYPelsPerMeter;
    unsigned int biClrUsed;
    unsigned int biClrImportant;
};
#pragma pack(pop)

// Класс изображения Пикачу
class PikachuImage {
private:
    int width;
    int height;
    std::vector<std::vector<Pixel>> pixels;

    bool isValid(int x, int y) const {
        return (x >= 0) && (x < width) && (y >= 0) && (y < height);
    }

    void setPixel(int x, int y, const Pixel& color) {
        if (isValid(x, y)) {
            pixels[y][x] = color;
        }
    }

    double sign(int x1, int y1, int x2, int y2, int x3, int y3) {
        return (double)(x1 - x3) * (y2 - y3) - (double)(x2 - x3) * (y1 - y3);
    }

    // Рисование заполненного эллипса
    void drawEllipse(int x1, int y1, int x2, int y2, const Pixel& color) {
        int centerX = (x1 + x2) / 2;
        int centerY = (y1 + y2) / 2;
        int radiusX = (x2 - x1) / 2;
        int radiusY = (y2 - y1) / 2;

        if (radiusX <= 0 || radiusY <= 0) return;

        for (int y = y1; y <= y2; y++) {
            for (int x = x1; x <= x2; x++) {
                double nx = (double)(x - centerX) / radiusX;
                double ny = (double)(y - centerY) / radiusY;
                if ((nx * nx + ny * ny) <= 1.0) {
                    setPixel(x, y, color);
                }
            }
        }
    }

    // Рисование заполненного круга
    void drawCircle(int cx, int cy, int radius, const Pixel& color) {
        for (int y = cy - radius; y <= cy + radius; y++) {
            for (int x = cx - radius; x <= cx + radius; x++) {
                int dx = x - cx;
                int dy = y - cy;
                if ((dx * dx + dy * dy) <= (radius * radius)) {
                    setPixel(x, y, color);
                }
            }
        }
    }

    // Рисование треугольника (ухо)
    void drawTriangle(int x1, int y1, int x2, int y2, int x3, int y3, const Pixel& color) {
        int minY = std::min({y1, y2, y3});
        int maxY = std::max({y1, y2, y3});

        for (int y = minY; y <= maxY; y++) {
            for (int x = 0; x < width; x++) {
                double d1 = sign(x, y, x1, y1, x2, y2);
                double d2 = sign(x, y, x2, y2, x3, y3);
                double d3 = sign(x, y, x3, y3, x1, y1);

                bool hasNeg = (d1 < 0) || (d2 < 0) || (d3 < 0);
                bool hasPos = (d1 > 0) || (d2 > 0) || (d3 > 0);

                if (!(hasNeg && hasPos)) {
                    setPixel(x, y, color);
                }
            }
        }
    }

public:
    PikachuImage(int w, int h) : width(w), height(h) {
        pixels.resize(height, std::vector<Pixel>(width));
    }

    // Получить пиксель
    Pixel getPixel(int x, int y) const {
        if (isValid(x, y)) return pixels[y][x];
        return Pixel();
    }

    // Нарисовать Пикачу
    void drawPikachu() {
        // Определяем цвета
        Pixel white(255, 255, 255);
        Pixel yellow(252, 220, 48);
        Pixel black(30, 30, 30);
        Pixel darkYellow(200, 170, 30);
        Pixel red(220, 50, 50);
        Pixel brown(120, 80, 40);
        Pixel pink(240, 150, 150);
        Pixel whiteEye(255, 255, 255);

        // Заполняем белым фоном
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                pixels[y][x] = white;
            }
        }

        // Рисуем Пикачу по координатам (для 128x128)
        // Левое ухо (треугольник)
        drawTriangle(15, 55, 25, 15, 45, 50, yellow);
        drawTriangle(15, 55, 20, 25, 35, 50, black);

        // Правое ухо (треугольник)
        drawTriangle(113, 55, 103, 15, 83, 50, yellow);
        drawTriangle(113, 55, 108, 25, 93, 50, black);

        // Голова (большой эллипс)
        drawEllipse(25, 45, 103, 115, yellow);

        // Контур головы
        drawEllipse(25, 45, 103, 115, black);
        drawEllipse(27, 47, 101, 113, yellow);

        // Левый глаз (чёрный)
        drawCircle(50, 70, 10, black);
        drawCircle(47, 67, 4, whiteEye);

        // Правый глаз (чёрный)
        drawCircle(78, 70, 10, black);
        drawCircle(75, 67, 4, whiteEye);

        // Нос
        drawCircle(64, 78, 3, black);

        // Рот (улыбка)
        for (int x = 55; x <= 73; x++) {
            int y = 82 + abs(x - 64) / 3;
            setPixel(x, y, black);
        }

        // Язык (розовый)
        drawCircle(64, 92, 6, pink);

        // Щёки (красные круги)
        drawCircle(38, 85, 9, red);
        drawCircle(90, 85, 9, red);
    }

    // RLE сжатие по блок-схеме
    std::vector<std::vector<RLERecord>> compressRLE() const {
        std::vector<std::vector<RLERecord>> result(height);

        for (int i = 0; i < height; i++) {
            std::vector<RLERecord> rowRecords;

            if (width == 0) continue;

            Pixel current_r = pixels[i][0];
            int current_count = 1;

            for (int j = 1; j < width; j++) {
                Pixel temp_r = pixels[i][j];

                if (current_r == temp_r) {
                    current_count += 1;
                } else {
                    rowRecords.push_back(RLERecord(current_r, current_count));
                    current_r = temp_r;
                    current_count = 1;
                }
            }

            // Добавляем последнюю запись
            rowRecords.push_back(RLERecord(current_r, current_count));
            result[i] = rowRecords;
        }

        return result;
    }

    // Сохранение в BMP файл
    bool saveBMP(const std::string& filename) const {
        std::ofstream file(filename, std::ios::binary);
        if (!file) {
            std::cerr << "Не удалось создать файл: " << filename << std::endl;
            return false;
        }

        int rowSize = ((width * 3 + 3) / 4) * 4;
        int padding = rowSize - width * 3;
        int imageSize = rowSize * height;

        BMPFileHeader fileHeader;
        BMPInfoHeader infoHeader;

        fileHeader.bfType = 0x4D42;
        fileHeader.bfSize = sizeof(BMPFileHeader) + sizeof(BMPInfoHeader) + imageSize;
        fileHeader.bfReserved1 = 0;
        fileHeader.bfReserved2 = 0;
        fileHeader.bfOffBits = sizeof(BMPFileHeader) + sizeof(BMPInfoHeader);

        infoHeader.biSize = sizeof(BMPInfoHeader);
        infoHeader.biWidth = width;
        infoHeader.biHeight = height;
        infoHeader.biPlanes = 1;
        infoHeader.biBitCount = 24;
        infoHeader.biCompression = 0;
        infoHeader.biSizeImage = imageSize;
        infoHeader.biXPelsPerMeter = 0;
        infoHeader.biYPelsPerMeter = 0;
        infoHeader.biClrUsed = 0;
        infoHeader.biClrImportant = 0;

        file.write(reinterpret_cast<const char*>(&fileHeader), sizeof(fileHeader));
        file.write(reinterpret_cast<const char*>(&infoHeader), sizeof(infoHeader));

        std::vector<unsigned char> rowBuffer(rowSize, 0);

        for (int y = height - 1; y >= 0; y--) {
            for (int x = 0; x < width; x++) {
                int pos = x * 3;
                rowBuffer[pos] = pixels[y][x].b;
                rowBuffer[pos + 1] = pixels[y][x].g;
                rowBuffer[pos + 2] = pixels[y][x].r;
            }
            file.write(reinterpret_cast<const char*>(rowBuffer.data()), rowSize);
        }

        file.close();
        return true;
    }

    int getWidth() const { return width; }
    int getHeight() const { return height; }
};

// Вывод статистики RLE
void printRLEStats(const std::vector<std::vector<RLERecord>>& rleData) {
    int totalRecords = 0;
    int totalPixels = 0;

    for (size_t i = 0; i < rleData.size(); i++) {
        totalRecords += (int)rleData[i].size();
        for (size_t j = 0; j < rleData[i].size(); j++) {
            totalPixels += rleData[i][j].count;
        }
    }

    std::cout << "\n=== СТАТИСТИКА RLE СЖАТИЯ ===" << std::endl;
    std::cout << "Всего пикселей: " << totalPixels << std::endl;
    std::cout << "Всего RLE записей: " << totalRecords << std::endl;
    if (totalRecords > 0) {
        std::cout << "Средняя длина серии: " << (double)totalPixels / totalRecords << std::endl;
        std::cout << "Коэффициент сжатия: " << (double)totalRecords / totalPixels * 100 << "%" << std::endl;
    }
}

// Вывод примера RLE записей
void printRLEExample(const std::vector<std::vector<RLERecord>>& rleData, int rows = 5) {
    std::cout << "\n=== ПРИМЕР RLE ЗАПИСЕЙ (первые " << rows << " строк) ===" << std::endl;

    int maxRows = std::min((int)rleData.size(), rows);
    for (int i = 0; i < maxRows; i++) {
        std::cout << "\nСтрока " << i << ": ";
        int count = 0;
        for (size_t j = 0; j < rleData[i].size(); j++) {
            if (count++ > 10) {
                std::cout << "...";
                break;
            }
            std::cout << "["
                      << (int)rleData[i][j].color.r << ","
                      << (int)rleData[i][j].color.g << ","
                      << (int)rleData[i][j].color.b
                      << "x" << rleData[i][j].count << "] ";
        }
    }
}

// Главная функция
int main() {
    SetConsoleOutputCP(1251);

    std::cout << "=== ГЕНЕРАТОР PIKACHU С RLE СЖАТИЕМ ===" << std::endl;

    int width = 128;
    int height = 128;

    std::cout << "\nСоздание изображения " << width << "x" << height << "..." << std::endl;

    PikachuImage image(width, height);

    std::cout << "Рисование Пикачу..." << std::endl;
    image.drawPikachu();

    std::cout << "Применение RLE сжатия..." << std::endl;
    std::vector<std::vector<RLERecord>> rleData = image.compressRLE();

    printRLEStats(rleData);
    printRLEExample(rleData);

    std::string filename = "pikachu.bmp";
    std::cout << "\nСохранение в файл: " << filename << std::endl;

    if (image.saveBMP(filename)) {
        std::cout << "Изображение успешно сохранено!" << std::endl;
        std::cout << "Откройте файл " << filename << " в Paint." << std::endl;
    } else {
        std::cout << "Ошибка при сохранении!" << std::endl;
    }

    std::cout << "\nНажмите Enter для выхода..." << std::endl;
    std::cin.get();

    return 0;
}