Let us formalize the problem. We are given $N$ slingshots, where slingshot $i$ has parameters $(x_i, y_i, t_i)$; we are also $M$ queries. Query $j$ has parameters $(a_i, b_i)$, and we are asked to determine
Fix some query $j$. There are four cases for the location of the best slingshot $i$. It may satisfy:
Each case corresponds to a "quadrant" relative to the query. If we can find, for each quadrant, the minimum cost of query $j$ if we use a slingshot in that quadrant, then the answer for query $j$ is simply the minimum of the four quadrant-specific minima.
Consider some slingshot $i$ which falls into the first case, for query $j$. Then the cost of using slingshot $i$ for query $j$ is
To compute this quantity for all queries, sweep left-to-right. Then when a query is encountered, we wish to find the minimum $t_i - x_i - y_i$ over all slingshots which have been encountered already and satisfy $b_j > y_i$. Such queries can be answered efficiently by maintaining a segment tree; whenever a slingshot is encountered by the sweepline, the value $t_i - x_i - y_i$ is inserted with index $y_i$. Then the desired minimum can be obtained by a range minimum query.
The other three cases are analogous. Note that the coordinates $y_i$ must be compressed so that they can be used as indices into the segment tree.
Overall time complexity is $O((N+M) \log (N+M))$.
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define MAXN 100000 #define SEG (1<<18) #define INF 1000000000000000LL int N,Q; long long x[MAXN], y[MAXN], t[MAXN]; int cx[MAXN],cy[MAXN]; int cid[MAXN]; long long qx[MAXN],qy[MAXN],qt[MAXN]; int qcx[MAXN],qcy[MAXN]; int qid[MAXN]; class SegTree { public: long long seg[2*SEG]; int l[2*SEG],r[2*SEG]; int low,high; void init() { for(int i=SEG;i<2*SEG;i++) { seg[i] = -INF; l[i] = r[i] = i-SEG; } for(int i=SEG-1;i>0;i--) { seg[i] = -INF; l[i] = l[2*i], r[i] = r[2*i+1]; } } void update(int i,long long v) { i += SEG; for(;i>0;i/=2) seg[i] = max(seg[i],v); } long long getMax(int i) { if((l[i]>high)||(r[i]<low)) return -INF; if((l[i]>=low)&&(r[i]<=high)) return seg[i]; return max(getMax(2*i),getMax(2*i+1)); } }; bool cmp(int a,int b) { return x[a]<x[b]; } bool qcmp(int a,int b) { return qx[a]<qx[b]; } long long ansLeft[MAXN]; long long ansRight[MAXN]; int main() { cin >> N >> Q; vector<long long> vx,vy; for(int i=0;i<N;i++) { cin >> x[i] >> y[i] >> t[i]; vx.push_back(x[i]); vy.push_back(y[i]); cid[i] = i; } sort(cid,cid+N,cmp); for(int i=0;i<Q;i++) { cin >> qx[i] >> qy[i]; vx.push_back(qx[i]); vy.push_back(qy[i]); qid[i] = i; } sort(qid,qid+Q,qcmp); sort(vx.begin(),vx.end()); sort(vy.begin(),vy.end()); vx.resize(distance(vx.begin(),unique(vx.begin(),vx.end()))); vy.resize(distance(vy.begin(),unique(vy.begin(),vy.end()))); for(int i=0;i<N;i++) { cx[i] = lower_bound(vx.begin(),vx.end(),x[i]) - vx.begin(); cy[i] = lower_bound(vy.begin(),vy.end(),y[i]) - vy.begin(); } for(int i=0;i<Q;i++) { qcx[i] = lower_bound(vx.begin(),vx.end(),qx[i]) - vx.begin(); qcy[i] = lower_bound(vy.begin(),vy.end(),qy[i]) - vy.begin(); } SegTree up, down; up.init(); down.init(); int j = 0; for(int i=0;i<Q;i++) { int cur = qid[i]; while(j < N && x[cid[j]] <= qx[cur]) { down.update(cy[cid[j]], x[cid[j]]+y[cid[j]]-t[cid[j]]); up.update(cy[cid[j]], x[cid[j]]-y[cid[j]]-t[cid[j]]); j++; } down.low = 0, down.high = qcy[cur]; up.low = qcy[cur], up.high = vy.size()-1; ansLeft[cur] = min(qx[cur] + qy[cur] - down.getMax(1), qx[cur] - qy[cur] - up.getMax(1)); } up.init(); down.init(); j = N-1; for(int i=Q-1;i>=0;i--) { int cur = qid[i]; while(j>=0 && x[cid[j]] >= qx[cur]) { down.update(cy[cid[j]], -x[cid[j]]+y[cid[j]]-t[cid[j]]); up.update(cy[cid[j]], -x[cid[j]]-y[cid[j]]-t[cid[j]]); j--; } down.low = 0, down.high = qcy[cur]; up.low = qcy[cur], up.high = vy.size()-1; ansRight[cur] = min(-qx[cur] + qy[cur] - down.getMax(1), -qx[cur] - qy[cur] - up.getMax(1)); } for(int i=0;i<Q;i++) cout << min(min(ansLeft[i],ansRight[i]),(long long)abs(qx[i]-qy[i])) << '\n'; }