题解：AT1202Contest_k ± Beam

解题思路核心洞察：光束不相交的关键是构建一个平面直线图（Planar Straight-Line Graph），其中所有边（光束）仅在端点处相交。最大化光束数量的最优策略是构建一个三角剖分的子集，利用多边形的对角线性质确保不相交。符号分配策略：选择一个凸包顶点作为基准（如最右侧顶点），标记为 '+' 其他顶点按极角排序，交替分配 '+' 和 '-'，确保相邻顶点符号不同这种分配方式保证了凸包上相邻顶点可连接，且内部顶点可与凸包形成不相交的光束光束构建策略：首先连接凸包上所有相邻顶点（形成凸包边界）对于每个内部顶点，连接到凸包上两个相邻顶点（形成三角形，确保不相交）代码实现 cpp 运行 #include #include #include #include #include using namespace std;

// 定义点结构 struct Point { long long x, y; int idx; // 原始索引（1-based） Point() : x(0), y(0), idx(0) {} Point(long long x_, long long y_, int idx_) : x(x_), y(y_), idx(idx_) {} };

// 全局变量：用于极角排序的基准点 Point base;

// 叉积计算：(p2 - p1) × (p3 - p1) long long cross(const Point& p1, const Point& p2, const Point& p3) { return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x); }

// 计算两点之间的平方距离（避免浮点运算） long long dist_sq(const Point& a, const Point& b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); }

// 极角排序比较函数 bool polar_cmp(const Point& a, const Point& b) { long long c = cross(base, a, b); if (c != 0) { return c > 0; // 逆时针排序 } else { // 共线时，近的在前 return dist_sq(base, a) < dist_sq(base, b); } }

// 寻找凸包（Andrew算法） vector convex_hull(vector& points) { int n = points.size(); if (n <= 1) return points;

CPP

// 按x排序，x相同按y排序
sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
    return a.x != b.x ? a.x < b.x : a.y < b.y;
});

vector<Point> hull;
// 下凸包
for (int i = 0; i < n; ++i) {
    while (hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), points[i]) <= 0) {
        hull.pop_back();
    }
    hull.push_back(points[i]);
}
// 上凸包
int m = hull.size();
for (int i = n-2; i >= 0; --i) {
    while (hull.size() > m && cross(hull[hull.size()-2], hull.back(), points[i]) <= 0) {
        hull.pop_back();
    }
    hull.push_back(points[i]);
}
hull.pop_back();  // 移除重复的起点
return hull;

}

// 判断点是否在凸包内部（利用叉积符号） bool is_inside_convex_hull(const Point& p, const vector& hull) { int n = hull.size(); for (int i = 0; i < n; ++i) { Point a = hull[i]; Point b = hull[(i+1)%n]; if (cross(a, b, p) < 0) { // 点在边的右侧，不在凸包内 return false; } } return true; }

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

CPP

// 输入处理
long long W, H;
int N;
cin >> W >> H >> N;
vector<Point> points(N);
for (int i = 0; i < N; ++i) {
    cin >> points[i].x >> points[i].y;
    points[i].idx = i + 1;  // 索引从1开始
}

// 步骤1：寻找凸包
vector<Point> hull = convex_hull(points);
int h_size = hull.size();
vector<bool> is_on_hull(N + 1, false);  // 标记是否为凸包顶点（1-based）
for (const Point& p : hull) {
    is_on_hull[p.idx] = true;
}

// 步骤2：选择基准点（凸包最右侧顶点，若有多个选最上方）
base = hull[0];
for (const Point& p : hull) {
    if (p.x > base.x || (p.x == base.x && p.y > base.y)) {
        base = p;
    }
}

// 步骤3：按极角排序所有点
vector<Point> sorted_points = points;
sort(sorted_points.begin(), sorted_points.end(), polar_cmp);

// 步骤4：分配符号（交替分配+和-）
string S(N, ' ');
for (int i = 0; i < N; ++i) {
    int idx = sorted_points[i].idx - 1;  // 转换为0-based字符串索引
    S[idx] = (i % 2 == 0) ? '+' : '-';
}

// 步骤5：构建光束（边）
vector<pair<int, int>> edges;

// 5.1 连接凸包相邻顶点（形成凸包边界）
for (int i = 0; i < h_size; ++i) {
    int a = hull[i].idx;
    int b = hull[(i+1)%h_size].idx;
    edges.emplace_back(a, b);
}

// 5.2 为内部顶点添加两条边（连接到凸包上相邻顶点）
// 先构建凸包顶点的极角排序表
vector<Point> hull_sorted;
for (const Point& p : hull) {
    hull_sorted.push_back(p);
}
sort(hull_sorted.begin(), hull_sorted.end(), polar_cmp);
int h_sorted_size = hull_sorted.size();

// 遍历所有内部顶点
for (const Point& p : points) {
    if (is_on_hull[p.idx]) continue;  // 跳过凸包顶点
    
    // 找到凸包上极角最接近p的两个顶点
    int left = 0, right = h_sorted_size - 1;
    while (right - left > 1) {
        int mid = (left + right) / 2;
        long long c = cross(base, hull_sorted[mid], p);
        if (c > 0) {
            left = mid;
        } else {
            right = mid;
        }
    }
    
    // 连接p到这两个凸包顶点
    int a = hull_sorted[left].idx;
    int b = hull_sorted[right].idx;
    edges.emplace_back(p.idx, a);
    edges.emplace_back(p.idx, b);
}

// 步骤6：输出结果
cout << S << '\n';
cout << edges.size() << '\n';
for (const auto& [u, v] : edges) {
    cout << u << ' ' << v << '\n';
}

return 0;

} 好不容易找个能提交题解的题，过一次吧。

题解：AT1202Contest_k ± Beam

文章操作

相关推荐

评论

题解：AT1202Contest_k ± Beam