不是呀，这种题你写什么半平面交干什么\yiw？

每个粒子距离发射器的距离，可以看作一条一次函数，其中$x$轴是时间，$y$轴是距离。

显然，每个时刻两台发射器的领先的那个粒子都是唯一的——也就是当我们把这所有一次函数画到平面直角坐标系上时，对于每一个$x$，$y$最大的那一条直线。而这个是可以通过凸包维护下凸壳然后在$O(n)$时间内求出的。

比如说这是样例中$A$发射器中所有粒子的函数图像。维护的下凸壳，从原点到$A$点处是绿线，$AB$线段是蓝线，然后$B$点往后是橙线。

对$A$发射器与$B$发射器都这么维护完凸包后，只需要用two-pointers就可以找到交点的位置。（当然咯，你想用二分也没问题——但是明显双针更易于实现，并且反正凸包都是$O(n)$的了，用$O(n)$的two-pointers又有何关系呢？）

总复杂度$O(nk+n\log n)$，其中$n\log n$来自求凸包前预处理的排序复杂度。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,l,m,tx,ty,ox[50100],oy[50100];
bool cx[50100],cy[50100];
pair<int,int>px[50100],py[50100];
pair<int,double>sx[50100],sy[50100];
double meet(pair<int,int>x,pair<int,int>y){
	return -1.0*(x.second-y.second)/(x.first-y.first);
}
bool cmpx(int x,int y){
	return px[x]<px[y];
}
bool cmpy(int x,int y){
	return py[x]<py[y];
}
signed main(){
	scanf("%lld%lld%lld",&n,&l,&m);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&px[i].second,&px[i].first),px[i].second*=-px[i].first,ox[i]=i;
	for(int i=1;i<=n;i++)scanf("%lld%lld",&py[i].second,&py[i].first),py[i].second*=-py[i].first,oy[i]=i;
	sort(ox+1,ox+n+1,cmpx),sort(oy+1,oy+n+1,cmpy);
//	for(int i=1;i<=n;i++)printf("%lld ",ox[i]);puts("");
//	for(int i=1;i<=n;i++)printf("%lld ",oy[i]);puts("");
	for(int k=1;k<=m;k++){
		tx=ty=0;
		for(int i=1;i<=n;i++){
			if(cx[ox[i]])continue;
			while(tx&&px[ox[i]].first==px[ox[sx[tx].first]].first)tx--;
			while(tx>=2&&meet(px[ox[sx[tx-1].first]],px[ox[i]])<=sx[tx].second)tx--;
			double tim=0;
			if(tx)tim=meet(px[ox[sx[tx].first]],px[ox[i]]);
//			printf("%lld:(%lld,%lld):%lf\n",i,px[ox[i]].first,px[ox[i]].second,tim);
			if(tim<0)tx--,tim=0;
			sx[++tx]=make_pair(i,tim);
		}
//		for(int i=1;i<=tx;i++)printf("%lld %lf\n",ox[sx[i].first],sx[i].second);
		for(int i=1;i<=n;i++){
			if(cy[oy[i]])continue;
			while(ty&&py[oy[i]].first==py[oy[sy[ty].first]].first)ty--;
			while(ty>=2&&meet(py[oy[sy[ty-1].first]],py[oy[i]])<=sy[ty].second)ty--;
			double tim=0;
			if(ty)tim=meet(py[oy[sy[ty].first]],py[oy[i]]);
			if(tim<0)ty--,tim=0;
			sy[++ty]=make_pair(i,tim);
		}
//		for(int i=1;i<=tx;i++)printf("%lld %lf\n",oy[sy[i].first],sy[i].second);
		sx[tx+1]=make_pair(-1,0x3f3f3f3f3f3f3f3f);
		sy[ty+1]=make_pair(-1,0x3f3f3f3f3f3f3f3f);
		for(int i=1,j=1;i<=tx;i++){
			bool ok=false;
			for(;sy[j+1].second<=sx[i+1].second;j++){
				if(1.0*(l-px[ox[sx[i].first]].second-py[oy[sy[j].first]].second)/(px[ox[sx[i].first]].first+py[oy[sy[j].first]].first)>sy[j+1].second)continue;
				ok=true;
				printf("%lld %lld\n",ox[sx[i].first],oy[sy[j].first]);
				cx[ox[sx[i].first]]=cy[oy[sy[j].first]]=true;
				break;
			}
			if(ok)break;
			if(1.0*(l-px[ox[sx[i].first]].second-py[oy[sy[j].first]].second)/(px[ox[sx[i].first]].first+py[oy[sy[j].first]].first)>sx[i+1].second)continue;
			ok=true;
			printf("%lld %lld\n",ox[sx[i].first],oy[sy[j].first]);
			cx[ox[sx[i].first]]=cy[oy[sy[j].first]]=true;
			break;
		}
	}
	return 0;
}