传送门 https://www.luogu.org/problemnew/show/CF97B
题目翻译都有...... 注意要求限制所有的点数不超过 200000 个.
这题的做法其实非常的暴力...... 一开始想得乱七八糟的, 想到把互相离的比较近的那些点都添加上一些点, 形成一个垂直的形状, 不过这样好像没什么思路 orzzzz
考虑分治, 只要每次找到坐标在中间的那个点, 之后把其他所有的点向这条线做正投影就行了. 这样一定可以保证成立, 因为我们在分治的过程中, 逐步保证了靠得最近的几个点之间也满足情况, 这样的话比较远的点的情况就更容易被满足, 即可完成.
看一下代码.
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<iostream>
- #include<cmath>
- #include<set>
- #include<queue>
- #include<vector>
- #include<map>
- #define rep(i,a,n) for(int i = a;i <= n;i++)
- #define per(i,n,a) for(int i = n;i>= a;i--)
- #define enter putchar('\n')
- #define fr friend inline
- #define y1 poj
- #define mp make_pair
- #define pr pair<int,int>
- #define fi first
- #define sc second
- #define pb push_back
- #define lowbit(x) x & (-x)
- using namespace std;
- typedef long long ll;
- const int M = 200005;
- const int INF = 1000000009;
- const double eps = 1e-7;
- ll read()
- {
- ll ans = 0,op = 1;
- char ch = getchar();
- while(ch <'0' || ch> '9')
- {
- if(ch == '-') op = -1;
- ch = getchar();
- }
- while(ch>= '0' && ch <= '9')
- {
- ans *= 10;
- ans += ch - '0';
- ch = getchar();
- }
- return ans * op;
- }
- struct node
- {
- int x,y;
- bool operator <(const node &g) const
- {
- return x < g.x || (x == g.x && y < g.y);
- }
- bool operator == (const node &g) const
- {
- return x == g.x && y == g.y;
- }
- }a[M];
- int n,cnt;
- void solve(int l,int r)
- {
- if(l> r) return;
- int mid = (l+r)>> 1;
- rep(i,l,r)
- {
- if(a[mid].x == a[i].x) continue;
- a[++cnt].x = a[mid].x,a[cnt].y = a[i].y;
- }
- solve(l,mid-1),solve(mid+1,r);
- }
- int main()
- {
- n = read(),cnt = n;
- rep(i,1,n) a[i].x = read(),a[i].y = read();
- sort(a+1,a+1+n);
- solve(1,n);
- sort(a+1,a+1+cnt);
- int tot = unique(a+1,a+1+cnt) - a - 1;
- printf("%d\n",tot);
- rep(i,1,tot) printf("%d %d\n",a[i].x,a[i].y);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2876565.html