算法记录：杂项

struct Rect
{
    int x1, x2, y1, y2;  // 左下角(x1,y1) 右上角(x2,y2)
};

struct Edge
{
    int x1, y1, x2, y2;
    bool horizontal;  // true=水平边, false=垂直边
};

// 获取正方形的四条边: 下、上、左、右
vector<Edge> getEdges(const Rect& r)
{
    vector<Edge> edges(4);
    edges[0] = {r.x1, r.y1, r.x2, r.y1, true};   // 下边
    edges[1] = {r.x1, r.y2, r.x2, r.y2, true};   // 上边
    edges[2] = {r.x1, r.y1, r.x1, r.y2, false};  // 左边
    edges[3] = {r.x2, r.y1, r.x2, r.y2, false};  // 右边
    return edges;
}

// 判断两个区间是否重叠
bool overlap(int l1, int r1, int l2, int r2)
{
    return l1 <= r2 && l2 <= r1;
}

// 判断两个正方形是否完全重合
bool sameRect(const Rect& a, const Rect& b)
{
    return a.x1 == b.x1 && a.x2 == b.x2 && a.y1 == b.y1 && a.y2 == b.y2;
}

// 判断两个正方形的边是否有重合部分（长度>0）
bool edgeOverlap(const Rect& a, const Rect& b)
{
    // 检查水平边重合
    for (int ay : {a.y1, a.y2}) {
        for (int by : {b.y1, b.y2}) {
            if (ay == by) {
                int l = max(a.x1, b.x1), r = min(a.x2, b.x2);
                if (l < r) return true;  // 有长度>0的重合
            }
        }
    }
    // 检查垂直边重合
    for (int ax : {a.x1, a.x2}) {
        for (int bx : {b.x1, b.x2}) {
            if (ax == bx) {
                int l = max(a.y1, b.y1), r = min(a.y2, b.y2);
                if (l < r) return true;
            }
        }
    }
    return false;
}

// 判断是否为无穷交点
bool isInfinite(const Rect& a, const Rect& b)
{
    if (!overlap(a.x1, a.x2, b.x1, b.x2)) return false;
    if (!overlap(a.y1, a.y2, b.y1, b.y2)) return false;
    if (sameRect(a, b)) return true;
    return edgeOverlap(a, b);
}

// 计算两条边的交点
void intersectEdges(const Edge& e1, const Edge& e2, set<pii>& pts)
{
    // 只有一横一竖才可能相交
    if (e1.horizontal == e2.horizontal) return;
    
    const Edge *h = &e1, *v = &e2;
    if (!e1.horizontal) swap(h, v);  // 保证h是水平边，v是垂直边
    
    int y = h->y1;  // 水平边的y坐标
    int x = v->x1;  // 垂直边的x坐标
    
    // 检查交点是否在两条线段上
    if (x >= min(h->x1, h->x2) && x <= max(h->x1, h->x2) &&
        y >= min(v->y1, v->y2) && y <= max(v->y1, v->y2)) {
        pts.insert({x, y});
    }
}

void solve()
{
    vector<vector<int>> arr(2, vector<int>(4));
    cin >> arr;
    
    // 构建两个正方形
    Rect a = {min(arr[0][0], arr[0][2]), max(arr[0][0], arr[0][2]),
              min(arr[0][1], arr[0][3]), max(arr[0][1], arr[0][3])};
    Rect b = {min(arr[1][0], arr[1][2]), max(arr[1][0], arr[1][2]),
              min(arr[1][1], arr[1][3]), max(arr[1][1], arr[1][3])};
    
    // 判断无穷交点
    if (isInfinite(a, b)) {
        cout << "inf" << endl;
        return;
    }
    
    // 计算有限交点
    set<pii> pts;
    vector<Edge> ea = getEdges(a);
    vector<Edge> eb = getEdges(b);
    
    for (const auto& e1 : ea) {
        for (const auto& e2 : eb) {
            intersectEdges(e1, e2, pts);
        }
    }
    
    cout << pts.size() << endl;
}

string minRotation(const string& s)
{
// 空字符串直接返回
    if (s.empty())
    {
        return "";
    }

    int n = s.size();
    // 将字符串复制一份拼接，方便取循环移位
    // 例如 s = "bca", ss = "bcabca"
    // 那么从 ss[1] 开始取 n 个字符就是 "cab"
    string ss = s + s;
    
    // i 和 j 是两个候选的起始位置
    // k 表示从 i 和 j 开始已经匹配的长度
    int i = 0, j = 1, k = 0;
    
    // 找最小表示的起始位置
    while (i < n && j < n && k < n) 
    {
        // 比较从 i 和 j 开始的第 k 个字符
        if (ss[i + k] == ss[j + k]) 
        {
            // 字符相同，继续比较下一个
            k++;
        } 
        else if (ss[i + k] < ss[j + k]) 
        {
            // ss[i+k] < ss[j+k]，说明以 i 开头的循环移位更小
            // 所以 j 开头的这个候选不可能成为最小表示
            // 而且从 j 到 j+k 之间的所有位置都不可能比 i 更小
            // 可以直接跳到 j+k+1
            j += k + 1;
            k = 0;  // 重置匹配长度
            if (i == j) 
            {
                j++;  // 避免 i 和 j 相同
            }
        } 
        else 
        {
            // ss[i+k] > ss[j+k]，说明以 j 开头的循环移位更小
            // 所以 i 开头的这个候选不可能成为最小表示
            // 从 i 到 i+k 之间的所有位置都不可能比 j 更小
            i += k + 1;
            k = 0;
            if (i == j) 
            {
                i++;  // 避免 i 和 j 相同
            }
        }
    }
    
    // 最终 i 和 j 中较小的那个就是最小表示的起始位置
    int start = min(i, j);
    
    // 从 start 开始取 n 个字符就是最小表示
    return s.substr(start) + s.substr(0, start);
}