######
1. A house, which get the lowest coverage from any wifi access point.

we need to find the distance of that house from its nearest wifi access point.

2. if n >= m then

we can place the access point at every house

so the ans is 0.0

3. otherwise we should place the access points in between first house and last house.

4. if a house is at 1

another house is at 5

then we can place a wifi at 3

this wifi can serve both houses with maximum distance of 2

5. possible output is between 0 and 1000000

because, house number is between 0 to 1000000

and we have to place the wifi points between first and last house

6. u find an excellent explanation here, how to apply binary search and other algorithm to solve this kind of problems :

topCoder Tutorial : Turnpike

7. to get the decimal ans, i’ve run another binary search

for example, from the first binary search u find

lo = 4

hi = 5

multiplied it by 10

lo = 40

hi = 50

now run another binary between 40 and 50

output: hi / 10 . hi % 10

// http://uva.onlinejudge.org/external/115/11516.html // Runtime : 0.060s // Tag : binary search // @BEGIN_OF_SOURCE_CODE #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <cctype> #include <stack> #include <queue> #include <list> #include <vector> #include <map> #include <sstream> #include <cmath> #include <bitset> #include <utility> #include <set> #include <numeric> #define INT_MAX 2147483647 #define INT_MIN -2147483647 #define pi acos(-1.0) #define N 1000000 #define LL unsigned long long using namespace std; int n, m; int houseNo [100000 + 10]; bool check (int mid) { int used = 1; int wifirange = houseNo [0] + mid; for ( int i = 0; i < m; i++ ) { if ( houseNo [i] > wifirange ) { wifirange = houseNo [i] + mid; used++; } } return used <= n; } int main () { int testCase; scanf ("%d", &testCase); while ( testCase-- ) { scanf ("%d %d", &n, &m); for ( int i = 0; i < m; i++ ) scanf ("%d", &houseNo [i]); if ( n >= m ) { printf ("0.0\n"); continue; } sort (houseNo, houseNo + m); int lo = 0; int hi = N; while ( hi - lo > 1 ) { int mid = (lo + hi) / 2; if ( check (mid * 2) ) hi = mid; else lo = mid; } lo *= 10; hi *= 10; for ( int i = 0; i < m; i++ ) houseNo [i] *= 10; while ( hi - lo > 1 ) { int mid = (lo + hi) / 2; if ( check (mid * 2) ) hi = mid; else lo = mid; } printf ("%d.%d\n", hi / 10, hi % 10); } return 0; } // @END_OF_SOURCE_CODE

## One thought on “UVa : 11516 (WiFi)”