---

#include <SFML/Graphics.hpp>
#include <vector>
#include <algorithm>
#include <iostream>

struct Point {
    double x, y;
};

// Векторное (косое) произведение векторов AB и AC.
// > 0  — левый поворот (против часовой стрелки)
// = 0  — точки коллинеарны
// < 0  — правый поворот
double cross(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);
}

// Алгоритм Эндрю (monotone chain). Возвращает вершины оболочки
// в порядке против часовой стрелки.
std::vector<Point> andrewHull(std::vector<Point> pts) {
    int n = (int)pts.size();
    if (n < 2) return pts;

    std::sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });
    // Удалим дубликаты
    pts.erase(std::unique(pts.begin(), pts.end(),
        [](const Point& a, const Point& b){ return a.x == b.x && a.y == b.y; }),
        pts.end());
    n = (int)pts.size();
    if (n < 2) return pts;

    std::vector<Point> hull;
    hull.reserve(2 * n);

    // Нижняя оболочка
    for (const auto& p : pts) {
        while (hull.size() >= 2 &&
               cross(hull[hull.size() - 2], hull[hull.size() - 1], p) <= 0)
            hull.pop_back();
        hull.push_back(p);
    }

    // Верхняя оболочка
    int lower_size = (int)hull.size() + 1; // +1, т.к. последняя точка нижней = первая верхней
    for (int i = (int)pts.size() - 2; i >= 0; --i) {
        const Point& p = pts[i];
        while ((int)hull.size() >= lower_size &&
               cross(hull[hull.size() - 2], hull[hull.size() - 1], p) <= 0)
            hull.pop_back();
        hull.push_back(p);
    }

    hull.pop_back(); // последняя точка совпадает с первой
    return hull;
}

// Простая экранная "кнопка"
struct Button {
    sf::RectangleShape shape;
    sf::Text           label;
    bool contains(sf::Vector2i p) const {
        return shape.getGlobalBounds().contains((float)p.x, (float)p.y);
    }
};

int main() {
    const unsigned W = 900, H = 650;
    sf::RenderWindow window(sf::VideoMode(W, H), "Convex Hull — Andrew's algorithm");
    window.setFramerateLimit(60);

    sf::Font font;
    if (!font.loadFromFile("arial.ttf")) {
        // В Linux/Mac можно подставить другой шрифт, например:
        // font.loadFromFile("/usr/share/fonts/truetype/dejavu/DejaVuSans.ttf");
        std::cerr << "Warning: font not loaded, text will be invisible.\n";
    }

    // ----- Кнопки -----
    Button btnBuild, btnClear;
    auto makeButton = [&](Button& b, float x, const std::string& txt) {
        b.shape.setSize({110.f, 36.f});
        b.shape.setPosition(x, 12.f);
        b.shape.setFillColor(sf::Color(60, 60, 80));
        b.shape.setOutlineColor(sf::Color::White);
        b.shape.setOutlineThickness(1.f);
        b.label.setFont(font);
        b.label.setString(txt);
        b.label.setCharacterSize(18);
        b.label.setFillColor(sf::Color::White);
        sf::FloatRect tb = b.label.getLocalBounds();
        b.label.setPosition(x + 55.f - tb.width / 2.f - tb.left,
                            12.f + 18.f - tb.height / 2.f - tb.top);
    };
    makeButton(btnBuild, W - 240.f, "Build (B)");
    makeButton(btnClear, W - 120.f, "Clear (C)");

    // ----- Данные -----
    std::vector<Point> points;
    std::vector<Point> hull;
    const float AREA_TOP = 60.f; // верхняя граница рабочей области

    sf::Text hint(font);
    hint.setString("LMB — add point | B — build hull | C — clear");
    hint.setCharacterSize(16);
    hint.setFillColor(sf::Color::White);
    hint.setPosition(12.f, 20.f);

    // ----- Главный цикл -----
    while (window.isOpen()) {
        sf::Event ev;
        while (window.pollEvent(ev)) {
            if (ev.type == sf::Event::Closed) window.close();

            if (ev.type == sf::Event::MouseButtonPressed &&
                ev.mouseButton.button == sf::Mouse::Left) {
                sf::Vector2i m(ev.mouseButton.x, ev.mouseButton.y);
                if (btnBuild.contains(m)) {
                    hull = andrewHull(points);
                } else if (btnClear.contains(m)) {
                    points.clear();
                    hull.clear();
                } else if (m.y > AREA_TOP) {
                    points.push_back({(double)m.x, (double)m.y});
                }
            }

            if (ev.type == sf::Event::KeyPressed) {
                if (ev.key.code == sf::Keyboard::B) hull = andrewHull(points);
                if (ev.key.code == sf::Keyboard::C) { points.clear(); hull.clear(); }
                if (ev.key.code == sf::Keyboard::Escape) window.close();
            }
        }

        window.clear(sf::Color(30, 30, 40));

        // Рабочая область
        sf::RectangleShape area({(float)W, (float)H - AREA_TOP});
        area.setPosition(0.f, AREA_TOP);
        area.setFillColor(sf::Color(45, 45, 60));
        window.draw(area);

        // Выпуклая оболочка
        if (hull.size() >= 2) {
            sf::VertexArray poly(sf::LineStrip, hull.size() + 1);
            for (size_t i = 0; i < hull.size(); ++i)
                poly[i].position = sf::Vector2f((float)hull[i].x, (float)hull[i].y);
            poly[hull.size()].position = poly[0].position; // замкнуть
            for (size_t i = 0; i < poly.getVertexCount(); ++i)
                poly[i].color = sf::Color(80, 220, 120);
            window.draw(poly);

            // Полупрозрачная заливка (треугольный веер от первой вершины)
            if (hull.size() >= 3) {
                sf::VertexArray fill(sf::TrianglesFan, hull.size() + 1);
                fill[0].position = sf::Vector2f((float)hull[0].x, (float)hull[0].y);
                fill[0].color = sf::Color(80, 220, 120, 50);
                for (size_t i = 0; i < hull.size(); ++i) {
                    fill[i + 1].position = sf::Vector2f((float)hull[i].x, (float)hull[i].y);
                    fill[i + 1].color    = sf::Color(80, 220, 120, 50);
                }
                window.draw(fill);
            }
        }

        // Точки
        for (const auto& p : points) {
            sf::CircleShape c(5.f);
            c.setFillColor(sf::Color(255, 220, 80));
            c.setOrigin(5.f, 5.f);
            c.setPosition((float)p.x, (float)p.y);
            window.draw(c);
        }

        // Подсказка и кнопки
        window.draw(hint);
        window.draw(btnBuild.shape); window.draw(btnBuild.label);
        window.draw(btnClear.shape); window.draw(btnClear.label);

        window.display();
    }
    return 0;
}