题意：三维平面上有n个点，每个点的坐标为（x[i]，y[i]，z[i]），n为偶数
现在要求取n/2次，每次取走一对点（x,y），要求没有未被取走的点在以x和y为对角点的矩形中
要求给出任意一组合法方案
n<=5e4，abs(x[i],y[i],z[i])<=1e8
思路：我觉得托老爷的官方题解的google机翻已经够简明了
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef unsigned int uint; 5 typedef unsigned long long ull; 6 typedef pair<int,int> PII; 7 typedef pair<ll,ll> Pll; 8 typedef vector<int> VI; 9 typedef vector<PII> VII; 10 //typedef pair<ll,ll>P; 11 #define N 200010 12 #define M 200010 13 #define fi first 14 #define se second 15 #define MP make_pair 16 #define pb push_back 17 #define pi acos(-1) 18 #define mem(a,b) memset(a,b,sizeof(a)) 19 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++) 20 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--) 21 #define lowbit(x) x&(-x) 22 #define Rand (rand()*(1<<16)+rand()) 23 #define id(x) ((x)<=B?(x):m-n/(x)+1) 24 #define ls p<<1 25 #define rs p<<1|1 26 27 const ll MOD=1e9+7,inv2=(MOD+1)/2; 28 double eps=1e-6; 29 ll INF=1e15; 30 int dx[4]={-1,1,0,0}; 31 int dy[4]={0,0,-1,1}; 32 33 struct node 34 { 35 int x,y,z,id; 36 }a[N],b[N]; 37 38 bool cmp(node a,node b) 39 { 40 if(a.x!=b.x) return a.x<b.x; 41 if(a.y!=b.y) return a.y<b.y; 42 return a.z<b.z; 43 } 44 45 int read() 46 { 47 int v=0,f=1; 48 char c=getchar(); 49 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 50 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 51 return v*f; 52 } 53 54 int main() 55 { 56 int n=read(); 57 rep(i,1,n) 58 { 59 a[i].x=read(),a[i].y=read(),a[i].z=read(); 60 a[i].id=i; 61 } 62 sort(a+1,a+n+1,cmp); 63 int i,j,k,m=0; 64 for(i=1;i<=n;) 65 { 66 j=i; 67 while(j<=n&&a[i].x==a[j].x&&a[i].y==a[j].y) j++; 68 for(k=i;k+2<=j;k+=2) printf("%d %d ",a[k].id,a[k+1].id); 69 if(k==j-1) b[++m]=a[k]; 70 i=j; 71 } 72 n=0; 73 for(i=1;i<=m;) 74 { 75 j=i; 76 while(j<=m&&b[i].x==b[j].x) j++; 77 for(k=i;k+2<=j;k+=2) printf("%d %d ",b[k].id,b[k+1].id); 78 if(k==j-1) a[++n]=b[k]; 79 i=j; 80 } 81 for(i=1;i<=n;i+=2) printf("%d %d ",a[i].id,a[i+1].id); 82 return 0; 83 }