11516 – WiFi

Given a street (a straigt line), a set of houses (points on that line) and a number of wireless access points (not placed yet), find the minimum range required for the access points to cover all the houses.

A binary search solution:

• Given the houses’ positions and the ranges, we can find the required number of access points n'. It’s correct to calculate this using some greedy algorithm.
• If n' < n (we have extra access points), decrease the range. Otherwise, increase the range.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

const double eps = 10E-4;
vector<int> house;

int nPointReq(double d) {
	int n = 1;
	double covered = house[0] + d;
	for (size_t i = 0; i < house.size(); ++i)
		if (house[i] > covered)
			covered = house[i] + d, ++n;
	return n;
}

int main() {
	int nCase, nPoint, nHouse;
	cin >> nCase;
	cout.precision(1);
	while (nCase--) {
		// input
		cin >> nPoint >> nHouse;
		house.clear();
		for (int i = 0, d; i < nHouse; ++i)
			cin >> d, house.push_back(d);
		sort(house.begin(), house.end());
		// solve
		double lD = 0, mD, hD = house[house.size() - 1];
		do {
			mD = (hD + lD) / 2.0;
			if (nPointReq(mD) > nPoint)
				lD = mD;
			else
				hD = mD;
		} while (hD - lD > eps);
		cout << fixed << (round(mD * 10) / 20.0) << endl;
	}
	return 0;
}