SHARE
TWEET

Untitled

a guest Sep 19th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. bool chk(int dist, int x, vector<vector<int>> &dp1, vector<vector<int>> &dp2, int A, int B){
  2.     unordered_set<int> st;
  3.     queue<int> q;
  4.     q.push(x);
  5.     while(!q.empty()){
  6.         auto z = q.front();
  7.         q.pop();
  8.         st.insert(z);
  9.         for(int i=0;i<B;i++)
  10.             if(dp1[i][x]<=dist && st.find(i)==st.end())
  11.                 q.push(i);
  12.     }
  13.     for(int i=0;i<A;i++){
  14.         int mn=INT_MAX;
  15.         for(auto it=st.begin();it!=st.end();it++)
  16.             mn=min(mn, dp2[(*it)][i]);
  17.         if(mn>dist)
  18.             return 0;
  19.     }
  20.     return 1;
  21. }
  22. int Solution::solve(int A, int B, vector<vector<int> > &C, vector<vector<int> > &D) {
  23.     vector<vector<int>> dp1(B, vector<int>(B));
  24.     for(int i=0;i<B;i++){
  25.         for(int j=0;j<B;j++){
  26.             dp1[i][j] = (D[i][0]-D[j][0])^2+(D[i][1]-D[j][1])^2;
  27.         }
  28.     }
  29.     vector<vector<int>> dp2(B, vector<int>(A));
  30.     for(int i=0;i<B;i++)
  31.         for(int j=0;j<A;j++)
  32.             dp2[i][j] = (D[i][0]-C[j][0])^2+(D[i][1]-C[j][1])^2;
  33.     int ans = INT_MAX;
  34.     for(int i=0;i<B;i++){
  35.         int mx=INT_MIN;
  36.         for(int j=0;j<A;j++)
  37.             mx = max(mx, dp2[i][j]);
  38.         int low=1, high = mx;
  39.         mx = INT_MAX;
  40.         while(low<=high){
  41.             int mid = (low+high)/2;
  42.             if(chk(mid, i, dp1, dp2, A, B)){
  43.                 mx=min(mx, mid);
  44.                 // cout<<"x";
  45.                 high=mid-1;
  46.             }
  47.             else
  48.                 low = mid+1;
  49.         }
  50.         ans=min(ans, mx);
  51.     }
  52.     return ans;
  53. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top