---

// ============================================================================
//  Лабораторная работа №5 — Выпуклая оболочка (алгоритм Грэхема)
//  Windows GUI приложение на Win32 API
// ============================================================================

#include <windows.h>
#include <vector>
#include <algorithm>

using namespace std;

// ============================================================================
//  Константы
// ============================================================================

const int BUTTON_ID        = 1;
const int WINDOW_WIDTH     = 900;
const int WINDOW_HEIGHT    = 650;
const int BUTTON_X         = 10;
const int BUTTON_Y         = 10;
const int BUTTON_WIDTH     = 180;
const int BUTTON_HEIGHT    = 35;
const int TEXT_X           = 210;
const int TEXT_Y           = 18;
const int DRAW_AREA_Y      = 55;
const int POINT_RADIUS     = 4;
const int HULL_PEN_WIDTH   = 3;

// ============================================================================
//  Структуры данных
// ============================================================================

struct Point {
    int x;
    int y;

    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }

    bool operator<(const Point& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};

// ============================================================================
//  Глобальные переменные
// ============================================================================

vector<Point> points;
vector<Point> hull;
HWND          buttonBuild;

// ============================================================================
//  Вспомогательные функции (геометрия)
// ============================================================================

/// Векторное произведение (a->b) x (a->c)
long long cross(const Point& a, const Point& b, const Point& c) {
    return 1LL * (b.x - a.x) * (c.y - a.y)
         - 1LL * (b.y - a.y) * (c.x - a.x);
}

/// Квадрат расстояния между двумя точками
long long dist2(const Point& a, const Point& b) {
    return 1LL * (a.x - b.x) * (a.x - b.x)
         + 1LL * (a.y - b.y) * (a.y - b.y);
}

// ============================================================================
//  Алгоритм Грэхема — построение выпуклой оболочки
// ============================================================================

vector<Point> grahamHull(vector<Point> p) {
    // Базовые случаи
    if (p.size() <= 1) return p;

    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());

    if (p.size() <= 2) return p;

    // Находим самую нижнюю (и левую) точку
    int start = 0;
    for (int i = 1; i < (int)p.size(); i++) {
        if (p[i].y < p[start].y ||
           (p[i].y == p[start].y && p[i].x < p[start].x)) {
            start = i;
        }
    }
    swap(p[0], p[start]);

    // Сортируем остальные точки по полярному углу
    Point base = p[0];
    sort(p.begin() + 1, p.end(), [base](const Point& a, const Point& b) {
        long long cr = cross(base, a, b);
        if (cr == 0) return dist2(base, a) < dist2(base, b);
        return cr > 0;
    });

    // Строим оболочку с помощью стека
    vector<Point> st;
    for (const Point& pt : p) {
        while (st.size() >= 2 &&
               cross(st[st.size() - 2], st[st.size() - 1], pt) <= 0) {
            st.pop_back();
        }
        st.push_back(pt);
    }

    return st;
}

// ============================================================================
//  Функции отрисовки
// ============================================================================

void drawPoint(HDC hdc, const Point& p) {
    Ellipse(hdc,
            p.x - POINT_RADIUS, p.y - POINT_RADIUS,
            p.x + POINT_RADIUS, p.y + POINT_RADIUS);
}

void drawHull(HDC hdc) {
    if (hull.size() < 2) return;

    HPEN pen     = CreatePen(PS_SOLID, HULL_PEN_WIDTH, RGB(255, 0, 0));
    HPEN oldPen  = (HPEN)SelectObject(hdc, pen);

    for (int i = 0; i < (int)hull.size(); i++) {
        Point a = hull[i];
        Point b = hull[(i + 1) % hull.size()];
        MoveToEx(hdc, a.x, a.y, NULL);
        LineTo(hdc, b.x, b.y);
    }

    SelectObject(hdc, oldPen);
    DeleteObject(pen);
}

// ============================================================================
//  Оконная процедура
// ============================================================================

LRESULT CALLBACK WindowProc(HWND hwnd, UINT msg, WPARAM wParam, LPARAM lParam) {
    switch (msg) {

    // --- Создание окна: инициализация кнопки ---
    case WM_CREATE:
        buttonBuild = CreateWindowW(
            L"BUTTON", L"Построить оболочку",
            WS_CHILD | WS_VISIBLE | BS_PUSHBUTTON,
            BUTTON_X, BUTTON_Y, BUTTON_WIDTH, BUTTON_HEIGHT,
            hwnd, (HMENU)(INT_PTR)BUTTON_ID, NULL, NULL);
        break;

    // --- Клик левой кнопкой мыши: добавление точки ---
    case WM_LBUTTONDOWN: {
        int x = LOWORD(lParam);
        int y = HIWORD(lParam);

        if (y > DRAW_AREA_Y) {
            points.push_back({x, y});
            hull.clear();
            InvalidateRect(hwnd, NULL, TRUE);
        }
        break;
    }

    // --- Команды от элементов управления ---
    case WM_COMMAND:
        if (LOWORD(wParam) == BUTTON_ID) {
            hull = grahamHull(points);
            InvalidateRect(hwnd, NULL, TRUE);
        }
        break;

    // --- Перерисовка окна ---
    case WM_PAINT: {
        PAINTSTRUCT ps;
        HDC hdc = BeginPaint(hwnd, &ps);
        SetBkMode(hdc, TRANSPARENT);

        // Подсказка
        const wchar_t text[] = L"Кликайте мышкой для добавления точек";
        TextOutW(hdc, TEXT_X, TEXT_Y, text, lstrlenW(text));

        // Точки (синие)
        HBRUSH pointBrush = CreateSolidBrush(RGB(0, 0, 255));
        HBRUSH oldBrush   = (HBRUSH)SelectObject(hdc, pointBrush);

        for (const Point& p : points) {
            drawPoint(hdc, p);
        }

        SelectObject(hdc, oldBrush);
        DeleteObject(pointBrush);

        // Оболочка (красная)
        drawHull(hdc);

        EndPaint(hwnd, &ps);
        break;
    }

    // --- Закрытие окна ---
    case WM_DESTROY:
        PostQuitMessage(0);
        break;

    default:
        return DefWindowProcW(hwnd, msg, wParam, lParam);
    }

    return 0;
}

// ============================================================================
//  Точка входа
// ============================================================================

int main() {
    HINSTANCE hInstance = GetModuleHandleW(NULL);

    // Регистрация класса окна
    const wchar_t CLASS_NAME[] = L"ConvexHullWindow";

    WNDCLASSW wc   = {};
    wc.lpfnWndProc   = WindowProc;
    wc.hInstance      = hInstance;
    wc.lpszClassName  = CLASS_NAME;
    wc.hbrBackground  = (HBRUSH)(COLOR_WINDOW + 1);
    wc.hCursor        = LoadCursor(NULL, IDC_ARROW);

    if (!RegisterClassW(&wc)) {
        MessageBoxW(NULL, L"Ошибка регистрации класса окна",
                    L"Ошибка", MB_OK | MB_ICONERROR);
        return 1;
    }

    // Создание окна
    HWND hwnd = CreateWindowExW(
        0, CLASS_NAME,
        L"Лабораторная работа №5 — Выпуклая оболочка. Алгоритм Грэхема",
        WS_OVERLAPPEDWINDOW,
        CW_USEDEFAULT, CW_USEDEFAULT,
        WINDOW_WIDTH, WINDOW_HEIGHT,
        NULL, NULL, hInstance, NULL);

    if (hwnd == NULL) {
        MessageBoxW(NULL, L"Ошибка создания окна",
                    L"Ошибка", MB_OK | MB_ICONERROR);
        return 1;
    }

    // Показ и запуск цикла сообщений
    ShowWindow(hwnd, SW_SHOW);
    UpdateWindow(hwnd);

    MSG msg = {};
    while (GetMessageW(&msg, NULL, 0, 0) > 0) {
        TranslateMessage(&msg);
        DispatchMessageW(&msg);
    }

    return 0;
}