fork(2) 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
stdin
Standard input is empty
stdout
Standard output is empty