点集:给定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 题解《挑战程序设计竞赛》