Codeforces 97B Superset 题解《挑战程序设计竞赛》

Codeforces 97B Superset 

点集：给定n个点，请添加一些点，使任意两点满足①在同一条水平线或竖直线上②或构成一个矩形框住其他点。

4.6划分、解决、合并：分治法 

平面上的分治法 

从子问题点集中间做一条垂直分割线，当前子问题的所有点在分割线上的投影即为要添加的新点。

由于这些新点都与原来的点在一条水平线上，所以一定满足①。不断迭代，使得原来所有点都被这种分割线处理过。

每个点与其投影满足条件①，非投影点构成矩形内部至少一定有个投影点，满足②，于是问题解决。

#include <iostream>
#include <set>
#include <algorithm>

using namespace std;
pair<int, int> point[10001];    // 输入点
set<pair<int, int>> all;
int n;

void dfs(int l, int r)
{
    int mid = (l + r) >> 1, mid_x = point[mid].first;         // 分割线
    for (int i = l; i <= r; i++)
    {
        all.emplace(pair<int, int>(mid_x, point[i].second));  // 投影
    }
    if (l < mid)
    {
        dfs(l, mid - 1);
    }
    if (mid < r)
    {
        dfs(mid + 1, r);
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &point[i].first, &point[i].second);
    }
    sort(point, point + n);
    dfs(0, n - 1);
    printf("%d\n", all.size());
    for (auto &p : all)
    {
        printf("%d %d\n", p.first, p.second);
    }
    return 0;
}

 知识共享署名-非商业性使用-相同方式共享：码农场 » Codeforces 97B Superset 题解《挑战程序设计竞赛》