题意分析

题目要求给定一个有限点集，只能用与坐标轴平行或倾斜45°的线段将它包围起来（必须闭合），要求找对最小的线段的集合。

解题思路

在考虑这个问题时，因为与常见的凸包问题解决方案不同，所以考虑能不能转化为标准的凸包问题

原问题要求凸包的每条边必须是 水平（Δy=0）、垂直（Δx=0）或45度（|Δx|=|Δy|） 方向。我们通过线性变换：
[ u = x + y, \quad v = x - y ]
将原坐标系 ((x, y)) 转换为新坐标系 ((u, v))。此时，原坐标系中的方向约束在新坐标系下具有明确的几何意义：

• 原坐标系的 45度边 对应新坐标系的 水平/垂直边（Δu=0 或 Δv=0）。
• 原坐标系的 水平/垂直边 对应新坐标系的 对角线边（Δu=±Δv）。

通过这种变换，原问题中允许的三种边方向，在新坐标系下统一为 水平、垂直或对角线（斜率±1） 的边。

在新坐标系 ((u, v)) 下，标准凸包算法可以直接计算点集的凸包。此时，凸包的边具有以下性质：

• 若凸包边是水平或垂直的（Δu=0 或 Δv=0）：对应原坐标系的45度边，满足方向约束。
• 若凸包边是对角线（Δu=±Δv）：对应原坐标系的水平或垂直边，也满足方向约束。

因此，新坐标系下的凸包顶点转换回原坐标系后，必然构成满足方向约束的凸多边形。这是因为：

• 坐标变换是线性的，保持凸性不变；
• 凸包边在新坐标系下的几何意义直接对应原问题的允许方向。

计算新坐标系下的凸包后，需通过逆变换回到原坐标系：
[ x = \frac{u + v}{2}, \quad y = \frac{u - v}{2} ]
此外，由于凸包算法可能返回顺时针或逆时针顺序的顶点，需通过反转顺序确保方向一致性（题目要求逆时针顺序）。

标程

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Point {
    long long x, y;
    Point(long long x = 0, long long y = 0) : x(x), y(y) {}
    bool operator<(const Point& other) const {
        return x < other.x || (x == other.x && y < other.y);
    }
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 坐标变换：(x,y) -> (u,v) = (x+y, x-y)
struct UVPoint {
    long long u, v;
    UVPoint(long long x, long long y) : u(x + y), v(x - y) {}
    bool operator<(const UVPoint& other) const {
        return u < other.u || (u == other.u && v < other.v);
    }
};

// 叉积计算
long long cross(const Point& O, const Point& A, const Point& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

// UV坐标系叉积计算
long long crossUV(const UVPoint& O, const UVPoint& A, const UVPoint& B) {
    return (A.u - O.u) * (B.v - O.v) - (A.v - O.v) * (B.u - O.u);
}

// 计算UV坐标系的凸包
vector<UVPoint> convexHullUV(vector<UVPoint> points) {
    if (points.size() <= 1) return points;
    
    sort(points.begin(), points.end());
    vector<UVPoint> hull;
    int n = points.size();
    
    // 构建下凸包
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 && 
               crossUV(hull[hull.size()-2], hull.back(), points[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }
    
    // 构建上凸包
    int lower_size = hull.size();
    for (int i = n-2; i >= 0; i--) {
        while (hull.size() > lower_size && 
               crossUV(hull[hull.size()-2], hull.back(), points[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(points[i]);
    }
    
    // 移除最后一个点（与第一个点重复）
    hull.pop_back();
    return hull;
}

// 逆变换
vector<Point> transformBack(const vector<UVPoint>& uvHull) {
    vector<Point> hull;
    for (const auto& uv : uvHull) {
        // 由于u和v都是整数，且u+v和u-v都是偶数
        long long x = (uv.u + uv.v) / 2;
        long long y = (uv.u - uv.v) / 2;
        hull.emplace_back(x, y);
    }
    return hull;
}

// 确保逆时针顺序
vector<Point> ensureCounterClockwise(vector<Point> hull) {
    if (hull.size() <= 2) return hull;
    
    // 计算带符号面积
    long long area = 0;
    int n = hull.size();
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        area += hull[i].x * hull[j].y - hull[j].x * hull[i].y;
    }
    
    // 如果面积为负，说明是顺时针，需要反转
    if (area < 0) {
        reverse(hull.begin(), hull.end());
    }
    return hull;
}

// 移除连续共线点
vector<Point> removeCollinearPoints(vector<Point> hull) {
    if (hull.size() <= 2) return hull;
    
    vector<Point> result;
    result.push_back(hull[0]);
    
    for (int i = 1; i < hull.size(); i++) {
        // 添加当前点
        result.push_back(hull[i]);
        int k = result.size();
        
        // 检查是否有三个连续点共线
        while (k >= 3) {
            Point a = result[k-3];
            Point b = result[k-2];
            Point c = result[k-1];
            
            // 检查三点是否共线
            if (cross(a, b, c) == 0) {
                // 移除中间点
                result.erase(result.begin() + k-2);
                k--;
            } else {
                break;
            }
        }
    }
    
    // 检查首尾连接处
    while (result.size() >= 3) {
        Point a = result[result.size()-2];
        Point b = result.back();
        Point c = result[0];
        Point d = result[1];
        
        // 检查末尾三点
        if (cross(a, b, c) == 0) {
            result.pop_back();
        }
        // 检查开头三点
        else if (cross(b, c, d) == 0) {
            result.erase(result.begin());
        } else {
            break;
        }
    }
    
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    vector<Point> points;
    
    for (int i = 0; i < n; i++) {
        long long x, y;
        cin >> x >> y;
        points.emplace_back(x, y);
    }
    
    // 坐标变换
    vector<UVPoint> uvPoints;
    for (const auto& p : points) {
        uvPoints.emplace_back(p.x, p.y);
    }
    
    // 计算凸包
    vector<UVPoint> uvHull = convexHullUV(uvPoints);
    
    // 逆变换
    vector<Point> hull = transformBack(uvHull);
    
    // 确保逆时针顺序
    hull = ensureCounterClockwise(hull);
    
    // 移除连续共线点
    hull = removeCollinearPoints(hull);
    
    // 输出结果
    for (const auto& p : hull) {
        cout << p.x << " " << p.y << '\n';
    }
    
    return 0;
}