fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <unordered_set>
  3. using namespace std;
  4. typedef pair<int, int> pii;
  5. typedef long long ll;
  6. typedef pair<ll, ll> pll;
  7.  
  8. int S, P;
  9. int pa[501];
  10. vector<pii> v;
  11.  
  12. int find(int n) {
  13. 	if (pa[n] < 0) return n;
  14. 	return pa[n] = find(pa[n]);
  15. }
  16. void merge(int a, int b) {
  17. 	a = find(a);
  18. 	b = find(b);
  19. 	if (a == b) return;
  20. 	pa[a] = b;
  21. }
  22. double dist(int i, int j) {
  23. 	ll d1 = v[i].first - v[j].first;
  24. 	ll d2 = v[i].second - v[j].second;
  25. 	return sqrt(d1 * d1 + d2 * d2);
  26. }
  27.  
  28. bool chk(double d) {
  29. 	memset(pa, -1, sizeof(pa));
  30. 	for (int i = 0; i < P; i++)
  31. 		for (int j = i + 1; j < P; j++)
  32. 			if (dist(i, j) <= d)
  33. 				merge(i, j);
  34. 	int cnt = 0;
  35. 	for (int i = 0; i < P; i++) 
  36. 		if (pa[i] < 0) cnt++;
  37. 	return cnt <= S;
  38. }
  39.  
  40. int main() {
  41. //	ios::sync_with_stdio(false);
  42. //	cin.tie(0), cout.tie(0);
  43. 	int N; cin >> N;
  44. 	while (N--) {
  45. 		cin >> S >> P;
  46. 		v.clear(), v.resize(P);
  47. 		for (int i = 0; i < P; i++) 
  48. 			cin >> v[i].first >> v[i].second;
  49.  
  50. 		double lo = 0, hi = 1e9, mid;
  51. 		for (int i = 0; i < 100; i++){
  52. 			mid = (lo + hi) / 2;
  53. 			if (chk(mid)) hi = mid; 
  54. 			else lo = mid;
  55. 		}
  56. 		printf("%.2f", hi);
  57. 	}
  58. 	return 0;
  59. }
Success #stdin #stdout 0s 4180KB
comments (?)
stdin
copy 
1
2 4
0 100
0 300
0 600
150 750
stdout
copy 
212.13
https://ideone.com/vTcPhH
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!