fork(7) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1<<17;
  6. const long long INF = 2000000000000000007;
  7.  
  8. struct point {
  9. 	int p[2];
  10. 	bool operator !=(const point &a) const {
  11. 		return !(p[0]==a.p[0] && p[1]==a.p[1]);
  12. 	}
  13. };
  14.  
  15. struct kd_node {
  16. 	int axis,value;
  17. 	point p;
  18. 	kd_node *left, *right;
  19. };
  20.  
  21. struct cmp_points {
  22. 	int axis;
  23. 	cmp_points(){}
  24. 	cmp_points(int x): axis(x) {}
  25. 	bool operator () (const point &a, const point &b) const {
  26. 		return a.p[axis]<b.p[axis];
  27. 	}
  28. };
  29.  
  30. typedef kd_node* node_ptr;
  31.  
  32. int tests,n;
  33. point arr[N],pts[N];
  34. node_ptr root;
  35. long long ans;
  36.  
  37. long long squared_distance(point a, point b) {
  38. 	long long ans=0;
  39. 	for(int i=0;i<2;i++) ans+=(a.p[i]-b.p[i])*1ll*(a.p[i]-b.p[i]);
  40. 	return ans;
  41. }
  42.  
  43. void build_tree(node_ptr &node, int from, int to, int axis) {
  44. 	if(from>to) {
  45. 		node=NULL;
  46. 		return;
  47. 	}
  48.  
  49. 	node=new kd_node();
  50.  
  51. 	if(from==to) {
  52. 		node->p=arr[from];
  53. 		node->left=NULL;
  54. 		node->right=NULL;
  55. 		return;
  56. 	}
  57.  
  58. 	int mid=(from+to)/2;
  59.  
  60. 	nth_element(arr+from,arr+mid,arr+to+1,cmp_points(axis));
  61. 	node->value=arr[mid].p[axis];
  62. 	node->axis=axis;
  63. 	build_tree(node->left,from,mid,axis^1);
  64. 	build_tree(node->right,mid+1,to,axis^1);
  65. }
  66.  
  67. void nearest_neighbor(node_ptr node, point q, long long &ans) {
  68. 	if(node==NULL) return;
  69.  
  70. 	if(node->left==NULL && node->right==NULL) {
  71. 		if(q!=node->p) ans=min(ans,squared_distance(node->p,q));
  72. 		return;
  73. 	}
  74.  
  75. 	if(q.p[node->axis]<=node->value) {
  76. 		nearest_neighbor(node->left,q,ans);
  77. 		if(q.p[node->axis]+sqrt(ans)>=node->value) nearest_neighbor(node->right,q,ans);
  78. 	}
  79.  
  80. 	else {
  81. 		nearest_neighbor(node->right,q,ans);
  82. 		if(q.p[node->axis]-sqrt(ans)<=node->value) nearest_neighbor(node->left,q,ans);
  83. 	}
  84. }
  85.  
  86. int main() {
  87. 	int i;
  88.  
  89. 	scanf("%d", &tests);
  90. 	while(tests--) {
  91. 		scanf("%d", &n);
  92. 		for(i=1;i<=n;i++) {
  93. 			scanf("%d %d", &arr[i].p[0], &arr[i].p[1]);
  94. 			pts[i]=arr[i];
  95. 		}
  96.  
  97. 		build_tree(root,1,n,0);
  98.  
  99. 		for(i=1;i<=n;i++) {
  100. 			ans=INF;
  101. 			nearest_neighbor(root,pts[i],ans);
  102. 			printf("%lld\n", ans);
  103. 		}
  104. 	}
  105.  
  106. 	return 0;
  107. }
  108.  
Success #stdin #stdout 0s 17288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/yDBOyc
language:
C++14 (gcc 8.3)
created:
7 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!