While the problem may appear complex at first glance, it can be efficiently solved using a straightforward greedy method.

Both gangs have a common objective: maximizing their power. The key to achieving this lies in acquiring weapons with the highest strength. To do this, we simply sort the weapons based on their strength in descending order. As we iterate through the sorted weapons list, we allocate them to the nearest gang that still has available members. It's worth noting that if one gang is closer to a weapon but has exhausted its members, the other gang can rightfully claim it. The complexity is n*m log(n*m).

import java.util.*;

public class Solution{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt(); int m = sc.nextInt();

        ArrayList<int []> weapons= new ArrayList<>();
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++){
                weapons.add(new int[] {sc.nextInt(), i, j});
            }
        }

        Collections.sort(weapons, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o2[0], o1[0]);
            }
        });

        int x1= sc.nextInt(); int y1= sc.nextInt();

        int x2= sc.nextInt(); int y2= sc.nextInt();

        int k1= sc.nextInt(); int k2= sc.nextInt();

        long ans=0;
        for (int i=0; i<n*m && (k1>0 || k2>0); i++){
            int arr[]=weapons.get(i);
            int dist1= Math.abs(arr[1]-x1)+Math.abs(arr[2]-y1);
            int dist2= Math.abs(arr[1]-x2)+Math.abs(arr[2]-y2);
            if (k1!=0 && (k2==0 || dist1<dist2)){
                ans+=arr[0];
                k1--;
            }
            else {
                ans-=arr[0];
                k2--;
            }
        }

        if (ans>0) System.out.println(1);
        else if (ans<0) System.out.println(2);
        else System.out.println(0);
    }
} 

It is obvious that there are $$$n^2$$$ possible points available i.e., all $$$(x_i, y_j)$$$ pairs. And, we can observe that with the increase in radius, the number of points will either increase or remain the same, so the function (number of points inside) is monotonous with the radius. Hence, we can do a binary search on the radius.

Now, we just have to calculate the amount of points inside the circle for a given radius. Let's observe the function: $$$x^2 + y^2 = r^2$$$. In this, as $$$x$$$ increases, $$$y$$$ decreases. So, if we sort the arrays by squared values, then we can use two pointers to calculate the count, which takes linear time.

Hence the complexity: $$$\mathcal{O}(n \cdot \log{R})$$$

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

template <typename T> using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int int64_t
#define endl '\n'
#define sz(v) ((int) v.size())
#define all(v) v.begin(), v.end()
#define vi vector<int>
#define pii pair<int, int>
#define inf 2e18
#define ld long double

int max(int x, int y) { return x > y ? x : y; }
int min(int x, int y) { return x < y ? x : y; }

const int N = 1e6 + 7;
int x[N], y[N];

void solve() {
  int n, k;
  cin >> n >> k;
  for(int i = 0; i < n; i++) {
    cin >> x[i];
  }
  for(int i = 0; i < n; i++) {
    cin >> y[i];
  }
  sort(x, x + n, [&](auto& x, auto& y) {
    return abs(x) < abs(y);
  });
  sort(y, y + n, [&](auto& x, auto& y) {
    return abs(x) < abs(y);
  });
  ld low = 0, high = 2e9, eps = 1e-9;
  auto check = [&](ld r) {
    int j = n - 1, ans = 0;
    for(int i = 0; i < n; i++) {
      while(j >= 0 && r * r - x[i] * x[i] - y[j] * y[j] < eps * eps) {
        j--;
      }
      ans += j + 1;
    }
    return ans >= k;
  };
  while(high - low > eps) {
    ld mid = (high + low) / 2;
    if(check(mid)) high = mid;
    else low = mid;
  }
  ld ans = check(low) ? low : high;
  cout << fixed << setprecision(9) << ans;
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  #ifdef VRINTLE
    freopen("./tests/test_0.txt", "r", stdin);
    freopen("./out.txt", "w", stdout);
    freopen("./err.txt", "w", stderr);
  #endif
  int t = 1;
  cin >> t;
  while(t--) {
    solve();
    cout << endl;
  }
  return 0;
}