---

#ifndef UNICODE
#define UNICODE
#endif

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

// ============================================================================
// 1. ГЕОМЕТРИЧЕСКИЕ СТРУКТУРЫ И АЛГОРИТМЫ
// ============================================================================

struct Point {
    double x, y;
    bool operator==(const Point& other) const {
        return std::abs(x - other.x) < 1e-9 && std::abs(y - other.y) < 1e-9;
    }
};

struct Edge {
    Point p1, p2;
    bool operator==(const Edge& other) const {
        return (p1 == other.p1 && p2 == other.p2) || (p1 == other.p2 && p2 == other.p1);
    }
};

struct Triangle {
    Point p1, p2, p3;
};

// --- Функции для Триангуляции Делоне ---

bool isPointInsideCircumcircle(const Triangle& t, const Point& p) {
    double d = 2 * (t.p1.x * (t.p2.y - t.p3.y) + t.p2.x * (t.p3.y - t.p1.y) + t.p3.x * (t.p1.y - t.p2.y));
    if (std::abs(d) < 1e-9) return false;

    double ux = ((t.p1.x * t.p1.x + t.p1.y * t.p1.y) * (t.p2.y - t.p3.y) +
                 (t.p2.x * t.p2.x + t.p2.y * t.p2.y) * (t.p3.y - t.p1.y) +
                 (t.p3.x * t.p3.x + t.p3.y * t.p3.y) * (t.p1.y - t.p2.y)) / d;

    double uy = ((t.p1.x * t.p1.x + t.p1.y * t.p1.y) * (t.p3.x - t.p2.x) +
                 (t.p2.x * t.p2.x + t.p2.y * t.p2.y) * (t.p1.x - t.p3.x) +
                 (t.p3.x * t.p3.x + t.p3.y * t.p3.y) * (t.p2.x - t.p1.x)) / d;

    double r2 = (t.p1.x - ux) * (t.p1.x - ux) + (t.p1.y - uy) * (t.p1.y - uy);
    double dist2 = (p.x - ux) * (p.x - ux) + (p.y - uy) * (p.y - uy);

    return dist2 <= r2;
}

bool areTrianglesEqual(const Triangle& t1, const Triangle& t2) {
    auto hasPoint = [](const Triangle& t, const Point& p) {
        return t.p1 == p || t.p2 == p || t.p3 == p;
    };
    return hasPoint(t1, t2.p1) && hasPoint(t1, t2.p2) && hasPoint(t1, t2.p3);
}

std::vector<Triangle> bowyerWatson(const std::vector<Point>& points) {
    std::vector<Triangle> triangulation;
    if (points.size() < 3) return triangulation;

    // Супер-треугольник с запасом перекрывает рабочую область окна
    Point st1 = { 400, -5000 };
    Point st2 = { -5000, 5000 };
    Point st3 = { 5000, 5000 };
    triangulation.push_back({ st1, st2, st3 });

    for (const auto& p : points) {
        std::vector<Triangle> badTriangles;
        for (const auto& t : triangulation) {
            if (isPointInsideCircumcircle(t, p)) {
                badTriangles.push_back(t);
            }
        }

        std::vector<Edge> polygon;
        for (const auto& t : badTriangles) {
            Edge edges[3] = { {t.p1, t.p2}, {t.p2, t.p3}, {t.p3, t.p1} };
            for (int i = 0; i < 3; ++i) {
                bool isUnique = true;
                for (const auto& other_t : badTriangles) {
                    if (areTrianglesEqual(t, other_t)) continue;
                    Edge other_edges[3] = { {other_t.p1, other_t.p2}, {other_t.p2, other_t.p3}, {other_t.p3, other_t.p1} };
                    if (edges[i] == other_edges[0] || edges[i] == other_edges[1] || edges[i] == other_edges[2]) {
                        isUnique = false;
                        break;
                    }
                }
                if (isUnique) polygon.push_back(edges[i]);
            }
        }

        for (const auto& bad : badTriangles) {
            triangulation.erase(std::remove_if(triangulation.begin(), triangulation.end(), [&](const Triangle& t) {
                return areTrianglesEqual(t, bad);
            }), triangulation.end());
        }

        for (const auto& edge : polygon) {
            triangulation.push_back({ edge.p1, edge.p2, p });
        }
    }

    triangulation.erase(std::remove_if(triangulation.begin(), triangulation.end(), [&](const Triangle& t) {
        return (t.p1 == st1 || t.p1 == st2 || t.p1 == st3 ||
                t.p2 == st1 || t.p2 == st2 || t.p2 == st3 ||
                t.p3 == st1 || t.p3 == st2 || t.p3 == st3);
    }), triangulation.end());

    return triangulation;
}

// --- Функции для Выпуклой Оболочки (Алгоритм Эндрю) ---

double crossProduct(const Point& a, const Point& b, const Point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

std::vector<Point> buildConvexHull(std::vector<Point> pts) {
    if (pts.size() < 3) return pts;

    std::sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });

    std::vector<Point> lower, upper;
    for (const auto& p : pts) {
        while (lower.size() >= 2 && crossProduct(lower[lower.size() - 2], lower.back(), p) <= 0) {
            lower.pop_back();
        }
        lower.push_back(p);
    }
    for (auto it = pts.rbegin(); it != pts.rend(); ++it) {
        while (upper.size() >= 2 && crossProduct(upper[upper.size() - 2], upper.back(), *it) <= 0) {
            upper.pop_back();
        }
        upper.push_back(*it);
    }

    lower.pop_back();
    upper.pop_back();
    lower.insert(lower.end(), upper.begin(), upper.end());
    return lower;
}

// ============================================================================
// 2. РЕНДЕРИНГ И ИНТЕРФЕЙС WINDOWS (WIN32 API)
// ============================================================================

// Глобальный вектор для хранения точек, которые накликал пользователь
std::vector<Point> g_points;

LRESULT CALLBACK WindowProc(HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam) {
    switch (uMsg) {
    case WM_LBUTTONDOWN: {
        // Шаг А: Ловим координаты клика мыши
        double mouseX = static_cast<double>(LOWORD(lParam));
        double mouseY = static_cast<double>(HIWORD(lParam));
        
        g_points.push_back({ mouseX, mouseY });

        // Принудительно заставляем окно перерисоваться
        InvalidateRect(hWnd, NULL, TRUE);
        return 0;
    }
    case WM_PAINT: {
        PAINTSTRUCT ps;
        HDC hdc = BeginPaint(hWnd, &ps);

        // Включаем чистый белый фон
        HBRUSH hBg = CreateSolidBrush(RGB(255, 255, 255));
        FillRect(hdc, &ps.rcPaint, hBg);
        DeleteObject(hBg);

        // Если точек достаточно, запускаем расчеты и отрисовку геометрии
        if (g_points.size() >= 3) {
            std::vector<Triangle> triangles = bowyerWatson(g_points);
            std::vector<Point> hull = buildConvexHull(g_points);

            // 1. Рисуем Внутреннюю Триангуляцию (Тонкие Серые Линии)
            HPEN hTrianglePen = CreatePen(PS_SOLID, 1, RGB(180, 180, 180));
            HGDIOBJ hOldPen = SelectObject(hdc, hTrianglePen);

            for (const auto& t : triangles) {
                MoveToEx(hdc, static_cast<int>(t.p1.x), static_cast<int>(t.p1.y), NULL);
                LineTo(hdc, static_cast<int>(t.p2.x), static_cast<int>(t.p2.y));
                LineTo(hdc, static_cast<int>(t.p3.x), static_cast<int>(t.p3.y));
                LineTo(hdc, static_cast<int>(t.p1.x), static_cast<int>(t.p1.y));
            }

            // 2. Рисуем Выпуклую Оболочку (Жирные Красные Линии)
            HPEN hHullPen = CreatePen(PS_SOLID, 3, RGB(255, 0, 0));
            SelectObject(hdc, hHullPen);

            if (!hull.empty()) {
                MoveToEx(hdc, static_cast<int>(hull[0].x), static_cast<int>(hull[0].y), NULL);
                for (size_t i = 1; i < hull.size(); ++i) {
                    LineTo(hdc, static_cast<int>(hull[i].x), static_cast<int>(hull[i].y));
                }
                LineTo(hdc, static_cast<int>(hull[0].x), static_cast<int>(hull[0].y)); // Замыкаем контур
            }

            // Наводим порядок в памяти после перьев
            SelectObject(hdc, hOldPen);
            DeleteObject(hTrianglePen);
            DeleteObject(hHullPen);
        }

        // 3. Рисуем Сами Точки (Синие Кружочки поверх линий)
        HBRUSH hPointBrush = CreateSolidBrush(RGB(0, 0, 255));
        HGDIOBJ hOldBrush = SelectObject(hdc, hPointBrush);

        for (const auto& p : g_points) {
            int r = 5; // Радиус точки для отрисовки
            Ellipse(hdc, static_cast<int>(p.x) - r, static_cast<int>(p.y) - r, 
                         static_cast<int>(p.x) + r, static_cast<int>(p.y) + r);
        }

        SelectObject(hdc, hOldBrush);
        DeleteObject(hPointBrush);

        EndPaint(hWnd, &ps);
        return 0;
    }
    case WM_DESTROY:
        PostQuitMessage(0);
        return 0;
    }
    return DefWindowProc(hWnd, uMsg, wParam, lParam);
}

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nShowCmd) {
    const wchar_t CLASS_NAME[] = L"GeometrySubsystemWindow";

    WNDCLASS wc = {};
    wc.lpfnWndProc = WindowProc;
    wc.hInstance = hInstance;
    wc.lpszClassName = CLASS_NAME;
    wc.hCursor = LoadCursor(NULL, IDC_ARROW); // Чтобы мышка была видна как стрелка

    RegisterClass(&wc);

    HWND hWnd = CreateWindowEx(
        0, CLASS_NAME, L"Delaunay & Convex Hull Subsystem",
        WS_OVERLAPPEDWINDOW,
        CW_USEDEFAULT, CW_USEDEFAULT, 1024, 768, // Окно 1024x768
        NULL, NULL, hInstance, NULL
    );

    if (hWnd == NULL) return 0;

    ShowWindow(hWnd, nShowCmd);

    MSG msg = {};
    while (GetMessage(&msg, NULL, 0, 0)) {
        TranslateMessage(&msg);
        DispatchMessage(&msg);
    }

    return 0;
}