fork download
copy 
  1. #include<stdio.h>
  2. struct xy {int x, y;}a[1212];
  3. int n;
  4. bool is_in(xy a, xy b,int x) {
  5. 	int d = (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
  6. 	return d <= x;
  7. }
  8. bool is_gone[1212];
  9. int f(int w,int x) {
  10. 	is_gone[w] = 1;
  11. 	int res = 1, i;
  12. 	for (i = 0; i < n; i++) {
  13. 		if (is_gone[i])continue;
  14. 		if (!is_in(a[w], a[i], x))continue;
  15. 		res+=f(i,x);
  16. 	}
  17. 	return res;
  18. }
  19. int main() {
  20. 	scanf("%d", &n);
  21. 	for (int i = 0; i < n; i++)scanf("%d%d", &a[i].x, &a[i].y);
  22. 	long long s = 0, e = (long long)2*25000*25000, ans;
  23. 	while (s <= e) {
  24. 		long long m = (s + e) / 2;
  25. 		for (int i = 0; i < n; i++)is_gone[i] = 0;
  26. 		if (f(0,m)==n)ans = m, e = m - 1;
  27. 		else s = m + 1;
  28. 	}
  29. 	printf("%lld", ans);
  30. 	return 0;
  31. }
Success #stdin #stdout 0s 4260KB
comments (?)
stdin
copy 
4
1 3
5 4
7 2
6 1
stdout
copy 
17
https://ideone.com/mNRCpJ
language:
C++ (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!