放牧代码和思想
专注自然语言处理、机器学习算法
    博主不用扣扣,公事请博客留言,私事请微博私信。开源项目一律GitHub见,发错地方恕不回复,谢谢。

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

目录

97b.png挑战程序设计竞赛第二版.jpg

Codeforces 97B Superset 

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

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

平面上的分治法 

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

97b.png

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

97b2.png

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

#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;
}

hankcs.com 2017-01-28 下午8.31.24.png


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

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机