-
Notifications
You must be signed in to change notification settings - Fork 11
/
kattis_wifi.cpp
64 lines (59 loc) · 1.5 KB
/
kattis_wifi.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**Kattis - wifi
* BSTA + greedy. Pretty straightforward, remember to sort houses first.
*
* Time: O(100 * n), Space: O(n)
*/
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
#define fast_cin() \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
int n, m;
vector<int> houses;
bool workable(ld max_dist) {
ld covered_until = -1;
int counter = 0;
for (int i = 0; i < n; i++) {
if (covered_until >= houses[i]) {
continue;
}
counter++;
covered_until = houses[i] + 2*max_dist;
if (counter > m) {
return false;
}
}
return true;
}
int main() {
int num_tc;
fast_cin();
cin >> num_tc;
while (num_tc--) {
cin >> m >> n;
houses.resize(n);
for (int i = 0; i < n; i++) {
cin >> houses[i];
}
sort(houses.begin(), houses.end());
ld lo = 0, hi = 1e6;
for (int i = 0; i < 50; i++) {
ld mid = (lo + hi) / 2;
// cout << fixed << setprecision(6) << mid << endl;
if (workable(mid)) {
hi = mid;
} else {
lo = mid;
}
}
cout << fixed << setprecision(1) << hi << endl;
}
return 0;
}