fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MaxN = (int)1e6 + 10;
  6. const int INF = (int)1e9;
  7. const int MOD = (int)1e9 + 7;
  8.  
  9. int n, q;
  10. int x[MaxN], y[MaxN], r[MaxN];
  11. int add[MaxN];
  12.  
  13. bool inside(int i, int j) {
  14. 	long long ds = 1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j]);
  15. 	return r[i] >= r[j] && ds <= 1LL * (r[i] - r[j]) * (r[i] - r[j]);
  16. }
  17.  
  18. int getHigh(int x, int y) {
  19. 	long long dist2 = 1LL * x * x + 1LL * y * y;
  20. 	long long dist = (int)sqrtl(dist2);
  21. 	while (dist >= 1 && (dist - 1) * (dist - 1) >= dist2) {
  22. 		--dist;
  23. 	}
  24. 	while (dist * dist < dist2) {
  25. 		++dist;
  26. 	}
  27. 	return dist;
  28. }
  29.  
  30. int getLow(int x, int y) {
  31. 	long long dist2 = 1LL * x * x + 1LL * y * y;
  32. 	long long dist = (int)sqrtl(dist2);
  33. 	while (dist >= 1 && (dist - 1) * (dist - 1) > dist2) {
  34. 		--dist;
  35. 	}
  36. 	while ((dist + 1) * (dist + 1) <= dist2) {
  37. 		++dist;
  38. 	}
  39. 	return dist;
  40. }
  41.  
  42. int main() {
  43. //	freopen("input.txt", "r", stdin);
  44. 	scanf("%d%d", &n, &q);
  45. 	for (int i = 1; i <= n; ++i) {
  46. 		scanf("%d%d%d", &x[i], &y[i], &r[i]);
  47. 	}
  48. 	for (int i = 1; i <= n; ++i) {
  49. 		for (int j = i + 1; j <= n; ++j) {
  50. 			int mi = 0;
  51. 			if (inside(i, j)) {
  52. 				mi = r[i] - (r[j] + getLow(x[i] - x[j], y[i] - y[j]));
  53. 			} else if (inside(j, i)) {
  54. 				mi = r[j] - (r[i] + getLow(x[i] - x[j], y[i] - y[j]));
  55. 			} else {
  56. 				mi = max(0, getHigh(x[i] - x[j], y[i] - y[j]) - (r[i] + r[j]));
  57. 			}
  58. 			int ma = getLow(x[i] - x[j], y[i] - y[j]) + (r[i] + r[j]);
  59. 			add[mi] += 1;
  60. 			add[ma + 1] -= 1;
  61. 		}
  62. 	}
  63. 	for (int i = 1; i < MaxN; ++i) {
  64. 		add[i] += add[i - 1];
  65. 	}
  66. 	while (q --> 0) {
  67. 		int x;
  68. 		scanf("%d", &x);
  69. 		printf("%d\n", add[x]);
  70. 	}
  71. 	return 0;
  72. }
  73.  
Success #stdin #stdout 0s 30864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/czl5Ap
language:
C++14 (gcc 8.3)
created:
5 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!