In this HackerEarth Wifi Routers problem solution IIIT Hyderabad is planning to install Wifi Routers in the campus to make it fully Wifi-enabled. Now each Wifi Router can only transmit data to a user or another WiFi Router only if the distance between Router and the receiving user/router is not more than R. Each Wifi Router has the same range R. A Wifi Router can get data from ground network or another Wifi Router. The aim here is that all the users get the data.

You have to find the minimal value of R that will ensure that all users get the data even if only one WiFi router is connected with ground network.


HackerEarth Wifi Routers problem solution


HackerEarth Wifi Routers problem solution.

#include <string> 
#include <assert.h>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <string.h>
using namespace std;

int main()
{
int t;
cin >> t;
while(t--)
{
int flag[109][109]={};
int nn,mm,temp1,temp2;
cin >> nn >> mm;
if(nn>=1 && nn<=100);
assert(mm>=0 && mm<=100);
vector<int> x;
vector<int> y;
vector<int> c;
for(int i=0; i<nn; i++){
cin >> temp1 >> temp2;
assert(temp1>=0 && temp1<=100);
assert(temp2>=0 && temp2<=100);
if(flag[temp1][temp2]==1)
assert(-1>0);
flag[temp1][temp2]=1;
x.push_back(temp1);y.push_back(temp2);c.push_back(1);
}

for(int i=0; i<mm; i++){
cin >> temp1 >> temp2;
assert(temp1>=0 && temp1<=100);
assert(temp2>=0 && temp2<=100);
if(flag[temp1][temp2]==1)
assert(-1>0);
flag[temp1][temp2]=1;
x.push_back(temp1);y.push_back(temp2);c.push_back(0);
}
assert((int)c.size() == (nn+mm));
int n=(int)x.size();

int d[n][n];

for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
d[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);

for (int i=0; i<n; i++) if (c[i]==0)
for (int j=0; j<n; j++)
for (int k=0; k<n; k++)
d[j][k]=min(d[j][k], max(d[j][i], d[i][k]));

int sol=0;

for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
if (c[i]==0 && c[j]==1)
sol=max(sol, d[i][j]);
printf("%.6lf\n",sqrt(sol));
}
}