题目翻译都有……注意要求限制所有的点数不超过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(' ') #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 ",tot); rep(i,1,tot) printf("%d %d ",a[i].x,a[i].y); return 0; }