#include <iostream>
#include <vector>

// 定义点的结构体，并重载运算符
struct Point {
    double x, y;
    // 构造函数（可选，但很方便）
    Point(double x = 0.0, double y = 0.0) : x(x), y(y) {}
    // 重载减法运算符 (P1 - P2)
    // 用于获取从 P2 指向 P1 的向量
    Point operator-(const Point& other) const {
        return Point(x - other.x, y - other.y);
    }
    // 重载加法运算符 (P1 + V1)
    // 用于将一个点按向量 V1 进行平移
    Point operator+(const Point& other) const {
        return Point(x + other.x, y + other.y);
    }
};

/**
 * @brief 使用射线法（水平）判断点是否在多边形内部
 * @param polygon 多边形的顶点（必须按顺序排列）
 * @param p       要测试的点
 * @return true 如果点在内部, false 如果点在外部或边上
 */
bool isInside(const std::vector<Point>& polygon, Point p) {
    int n = polygon.size();
    if (n < 3) {
        return false; // 不是一个有效的多边形
    }
    bool inside = false;
    // 遍历多边形的每一条边 (i, j)
    for (int i = 0, j = n - 1; i < n; j = i++) {
        Point p1 = polygon[i];
        Point p2 = polygon[j];
        // 1. 检查Y坐标是否跨越了射线的Y坐标
        if ( ((p1.y > p.y) != (p2.y > p.y)) ) {
            // 2. 计算射线与边的交点的 x 坐标
            // (x - p1.x) / (p2.x - p1.x) = (p.y - p1.y) / (p2.y - p1.y)
            // (p2.x - p1.x) 是向量 p1->p2 的 x 分量
            // (p2.y - p1.y) 是向量 p1->p2 的 y 分量
            // 尽管我们重载了运算符，但在这里直接使用 x, y 分量进行
            // 斜率和比例计算仍然是最清晰的。
            double intersectX = (p2.x - p1.x) * (p.y - p1.y) / (p2.y - p1.y) + p1.x;
            // 3. 检查交点是否在射线上（即在点的右侧）
            if (p.x < intersectX) {
                inside = !inside; // 翻转奇偶性
            }
        }
    }
    return inside;
}

int main() {
    // 使用新的构造函数初始化
    // 矩形 (0,0) -> (5,0) -> (5,5) -> (0,5)
    std::vector<Point> polygon = {{0, 0}, {5, 0}, {5, 5}, {0, 5}};

    // 凹多边形
    std::vector<Point> concave_polygon = {
        {0, 0}, {5, 0}, {5, 3}, {3, 3}, {3, 2}, {2, 2}, {2, 3}, {0, 3}
    };

    // --- 测试运算符重载 ---
    Point v1(1.0, 2.0);
    Point v2(3.0, 1.0);
    Point diff = v1 - v2; // diff 将是 (-2.0, 1.0)
    std::cout << "--- 运算符重载测试 ---" << std::endl;
    std::cout << "v1 - v2 = (" << diff.x << ", " << diff.y << ")" << std::endl;
    std::cout << "------------------------\n" << std::endl;


    // --- 测试点 ---
    Point p_inside(2.5, 2.5);  
    Point p_outside(10, 2.5); 
    Point p_on_edge(5, 2.5);   
    Point p_on_vertex(5, 5);   
    Point p_concave_in(1, 1);  
    Point p_concave_out(2.5, 2.5); 

    std::cout << std::boolalpha;

    std::cout << "--- 矩形测试 ---" << std::endl;
    std::cout << "点 (2.5, 2.5) 在内部吗? " << isInside(polygon, p_inside) << std::endl;  
    std::cout << "点 (10, 2.5) 在内部吗? " << isInside(polygon, p_outside) << std::endl; 
    std::cout << "点 (5, 2.5) 在内部吗? " << isInside(polygon, p_on_edge) << std::endl;   
    std::cout << "点 (5, 5) 在内部吗? " << isInside(polygon, p_on_vertex) << std::endl; 

    std::cout << "\n--- 凹多边形测试 ---" << std::endl;
    std::cout << "点 (1, 1) 在内部吗? " << isInside(concave_polygon, p_concave_in) << std::endl; 
    std::cout << "点 (2.5, 2.5) 在内部吗? " << isInside(concave_polygon, p_concave_out) << std::endl; 

    return 0;
}

template<typename T>
class Queue {
private:
    struct Node {
        T data;
        std::shared_ptr<Node> next;
        Node(const T& val) : data(val), next(nullptr) {}
    };

    std::shared_ptr<Node> front;  // 队首指针
    std::weak_ptr<Node> rear;     // 队尾指针（弱引用避免循环引用）
    size_t count;                 // 元素数量

public:
    // 构造函数
    Queue() : front(nullptr), rear(), count(0) {}

    // 禁用拷贝构造和赋值（防止浅拷贝问题）
    Queue(const Queue&) = delete;
    Queue& operator=(const Queue&) = delete;

    // 移动构造
    Queue(Queue&& other) noexcept 
        : front(std::move(other.front)), rear(other.rear), count(other.count) {
        other.count = 0;
    }

    // 移动赋值
    Queue& operator=(Queue&& other) noexcept {
        if (this != &other) {
            front = std::move(other.front);
            rear = other.rear;
            count = other.count;
            other.count = 0;
        }
        return *this;
    }

    // 析构函数（智能指针自动释放内存）
    ~Queue() = default;

    // 入队操作
    void enqueue(const T& val) {
        auto new_node = std::make_shared<Node>(val);
        if (empty()) {
            front = rear = new_node;
        } else {
            rear.lock()->next = new_node;
            rear = new_node;
        }
        ++count;
    }

    // 出队操作
    T dequeue() {
        if (empty()) {
            throw std::out_of_range("Queue is empty");
        }
        auto old_front = front;
        front = front->next;
        if (!front) {  // 如果队列变空
            rear.reset();
        }
        --count;
        return old_front->data;
    }

    // 查看队首元素
    T peek() const {
        if (empty()) {
            throw std::out_of_range("Queue is empty");
        }
        return front->data;
    }

    // 判断队列是否为空
    bool empty() const {
        return count == 0;
    }

    // 获取队列大小
    size_t size() const {
        return count;
    }

    // 打印队列内容（调试用）
    void print() const {
        auto current = front;
        while (current) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

// 实现一个先入先出的队列


template <typename T>
struct QueueNode {
    T data;
    QueueNode *next;
    QueueNode(const T& value) : data(value), next(nullptr) {} // 
};


template <typename T>
class Queue {
    public:
        Queue() {} // 构造函数
        ~Queue() {clear()} // 析构函数

        void push(const &T value) { // 入队方法
            // 创建一个新的Queue节点
            QueueNode<T>* new_node = new QueueNode<T>(value);
            if (size == 0) {
                front = new_node; // 新入队的节点就是front
            } else {
                rear->next = new_node;
                rear = new_node;
            }
            size++;
        }

        void pop() { // 出队方法
            // 将node 出队列
            if (size == 0) return; // 判空
            QueueNode<T> *temp_node = front;
            front = front->next; // 更新front指针
            delete temp_node; // 删除temp_node
            size--;
            if (size == 0) rear = nullptr; // 如果队列为空，则rear指针为nullptr
        }

        // 获取队列头

        T& getFront() {
            return front->data;
        }

        T& getRear() {
            return rear->data;
        }

        // 清空
        void clear() {
            while (size > 0) {
                pop();
            }
        }
    private:
        Queue<T>* front = nullptr; // 队列的头
        Queue<T>* rear = nullptr; // 队列的尾
        int size = 0; // 队列的长度
}

class Buffer {
    public:
        Buffer(Buffer&& other) noexcept : data(other.data) {
            other.data = nullptr; // 资源转移
        }
    private:
        int* data;
};

// 拷贝构造（深拷贝）
MyString(const MyString& other) : data(new char[other.size]) {
    std::copy(other.data, other.data + other.size, data);
}
// 移动构造（资源转移）
MyString(MyString&& other) noexcept : data(other.data) {
    other.data = nullptr;
}