题意：三维平面上有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\n",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\n",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\n",a[i].id,a[i+1].id);
82     return 0;
83 }