---

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

// ============================================================================
// 1. СТРУКТУРЫ ДАННЫХ
// ============================================================================

struct Point {
    double x, y;

    // Оператор сравнения точек с учетом погрешности типа double
    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;

    // Ребро AB и ребро BA — это одно и то же ребро
    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;
};

// ============================================================================
// 2. ГЕОМЕТРИЧЕСКИЕ ХЕЛПЕРЫ
// ============================================================================

// Проверка: находится ли точка P внутри описанной окружности треугольника T
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);
}

// ============================================================================
// 3. АЛГОРИТМ БОЙЕРА — ВАТСОНА (ТРИАНГУЛЯЦИЯ ДЕЛОНЕ)
// ============================================================================

std::vector<Triangle> bowyerWatson(const std::vector<Point>& points) {
    std::vector<Triangle> triangulation;

    // Шаг 1: Создаем супер-треугольник (временный внешний каркас)
    // Координаты выбраны с запасом для области экрана ~ 1000x1000
    Point st1 = { 500, -5000 };
    Point st2 = { -5000, 5000 };
    Point st3 = { 5000, 5000 };
    
    triangulation.push_back({ st1, st2, st3 });

    // Шаг 2: Инкрементно добавляем каждую точку пользователя
    for (const auto& p : points) {
        std::vector<Triangle> badTriangles;

        // Находим все треугольники, чьи окружности пробиты точкой p
        for (const auto& t : triangulation) {
            if (isPointInsideCircumcircle(t, p)) {
                badTriangles.push_back(t);
            }
        }

        // Шаг 3: Выделяем уникальные ребра (границу каверны)
        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]);
                }
            }
        }

        // Шаг 4: Удаляем старые плохие треугольники из основной сети
        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 });
        }
    }

    // Шаг 5: Очистка. Удаляем треугольники, связанные с супер-треугольником
    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;
}

// ============================================================================
// 4. ДЕМОНСТРАЦИЯ ЗАПУСКА
// ============================================================================

int main() {
    // Набор тестовых точек на плоскости
    std::vector<Point> points = {
        {150, 200}, {300, 100}, {450, 250}, {200, 400}, {350, 350}
    };

    // Строим триангуляцию Делоне
    std::vector<Triangle> mesh = bowyerWatson(points);

    // Вывод результатов в консоль
    std::cout << "Successfully built " << mesh.size() << " Delaunay triangles:\n\n";
    
    for (size_t i = 0; i < mesh.size(); ++i) {
        std::cout << "Triangle #" << i + 1 << ":\n"
                  << "  Vertex 1: (" << mesh[i].p1.x << ", " << mesh[i].p1.y << ")\n"
                  << "  Vertex 2: (" << mesh[i].p2.x << ", " << mesh[i].p2.y << ")\n"
                  << "  Vertex 3: (" << mesh[i].p3.x << ", " << mesh[i].p3.y << ")\n"
                  << "----------------------------------------\n";
    }

    return 0;
}