首页 > 代码库 > Codeforces 97B Superset 平面分治
Codeforces 97B Superset 平面分治
题目链接:点击打开链接
题意:
给定一个点集
添加一些点后再把这个点集输出来。
添加完点后使得对于点集内任意2个点都满足下面2条中至少一条
1、在同一水平线上或在同一垂直线上
2、所围成的矩阵里有其他点。
思路:
平面分治
先把点按x轴排序,然后找到中间的点,做一条直线 x = a[mid].x;
然后把所有点都投影到这条直线上,那么对于左边的点就不需要再和右边的进行匹配了。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <stdio.h> #include <algorithm> #include <iostream> #include <set> #include <queue> #include <cstring> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int inf = 1e9; template <class T> inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } #define N 10005 pii a[N], b[N*20]; int top, n; void dfs(int l, int r){ int mid = (l+r)>>1, maxx = a[mid].first; for(int i = l; i <= r; i++) b[top++] = pii(maxx, a[i].second); if(l < mid) dfs(l, mid-1); if(mid < r) dfs(mid+1, r); } void input(){ for(int i = 1; i <= n; i++) rd(a[i].first), rd(a[i].second); sort(a+1, a+1+n); top = 0; } void output(){ sort(b, b+top); top = unique(b, b+top)-b; pt(top); putchar('\n'); for(int i = 0; i < top; i++) pt(b[i].first), putchar(' '), pt(b[i].second), putchar('\n'); } int main(){ while(rd(n)){ input(); dfs(1, n); output(); } return 0; }
Codeforces 97B Superset 平面分治
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。