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