洛谷
首先进行分类讨论。
对于每个右上角的点，为了不让箭穿过箭靶，必须分配一只向下射的奶牛，即斜率为负数的奶牛。
右下角的点同理，只能选择斜率为正数的点。
对于左上角左下角，不管斜率为正还是负都可以射到。
那么无解条件明显就是斜率为正的和斜率为负的其中有一个不到 \(n\)。
但是我们的高度会受到射击点的 \(x\) 和 \(y\) 坐标以及奶牛的斜率 \(k\) 影响。
此时我们发现这并不好直接贪心处理。
但是我们可以发现题目所问的问题是最小的最大距离，明显可以二分。
那么我们可以二分两次，分别得到最低的最高点和最高的最低点。
我们二分出来一个最高点，再枚举每个斜率为负的需要射的点，此时计算出一个满足条件的最大斜率，分配小于等于这个斜率的最大斜率即可，可以用 set 维护。
那么最低点也是同理了。
但是对于左边的点又该怎么分配？
容易发现左边的点 \(x\) 都相等，那么有影响的只有 \(y\) 和 \(k\) 了，我们将 \(y\) 小的分给斜率为负的，\(y\) 大的分给斜率为正的即可。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,sx,a[160005],b[160005],cnta,cntb;
struct P{int x,y,yy;
}c[40005];
int d[80005];
multiset<int> s;
bool check(int mid){s.clear();for(int i=1;i<=cntb;i++)s.insert(-b[i]);for(int i=1;i<=n;i++){if(mid<c[i].yy)return false;auto it=s.upper_bound((mid-c[i].yy)/c[i].x);if(it==s.begin())return false;it--;s.erase(it);}for(int i=2*n;i>3*n-cntb;i--){if(mid<d[i])return false;auto it=s.upper_bound((mid-d[i])/sx);if(it==s.begin())return false;it--;s.erase(it);}return true;
}
bool check2(int mid){s.clear();for(int i=1;i<=cnta;i++)s.insert(a[i]);for(int i=1;i<=n;i++){if(mid>c[i].y)return false;auto it=s.upper_bound((c[i].y-mid)/c[i].x);if(it==s.begin())return false;it--;s.erase(it);}for(int i=1;i<=cnta-n;i++){if(mid>d[i])return false;auto it=s.upper_bound((d[i]-mid)/sx);if(it==s.begin())return false;it--;s.erase(it);}return true;
}
signed main(){cin>>T;while(T--){cnta=cntb=0;cin>>n>>sx;for(int i=1;i<=n;i++)cin>>c[i].y>>c[i].yy>>c[i].x;for(int i=1,x;i<=4*n;i++){cin>>x;if(x>0)a[++cnta]=x;else b[++cntb]=x;}if(cnta<n||cntb<n){cout<<-1<<endl;continue;}for(int i=1;i<=n;i++)d[i]=c[i].y,d[i+n]=c[i].yy;sort(d+1,d+2*n+1);int l=-1e18,r=1e18;while(l<=r){int mid=l+r>>1;if(check(mid))r=mid-1;else l=mid+1;}int res=r+1;l=-1e18,r=1e18;while(l<=r){int mid=l+r>>1;if(check2(mid))l=mid+1;else r=mid-1;}cout<<res-l+1<<endl;}return 0;
}