fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. const int MAX_N = 1e5 + 5;
  6. const ll INF = (ll) 2e18 + 5;
  7.  
  8. struct Point {
  9. 	int x[2];
  10.  
  11. 	ll CalculateDist(const Point &other) const {
  12. 		ll ans = 0;
  13.  
  14. 		for(int i = 0; i < 2; i++) {
  15. 			ans += 1ll * (x[i] - other.x[i]) * (x[i] - other.x[i]);	
  16. 		}
  17.  
  18. 		return ans;
  19. 	}
  20.  
  21. 	bool operator!= (const Point &other) const {
  22. 		for(int i = 0; i < 2; i++) {
  23. 			if(x[i] != other.x[i]) {
  24. 				return true;
  25. 			}
  26. 		}
  27.  
  28. 		return false;
  29. 	}
  30. };
  31.  
  32. struct ComparePoints {
  33. 	private:
  34. 		int axis;
  35.  
  36. 	public:
  37. 		ComparePoints(int axis = 0) {
  38. 			this -> axis = axis;
  39. 		}
  40.  
  41. 		bool operator () (const Point &p1, const Point &p2) const { 
  42. 			return p1.x[axis] < p2.x[axis];
  43. 		}
  44. };
  45.  
  46. struct Node {
  47. 	private:
  48. 		Point p;
  49. 		int axis;
  50. 		int value;
  51.  
  52. 		Node *left;
  53. 		Node *right;
  54.  
  55. 	public:
  56. 		Node() {
  57. 			this -> left = nullptr;
  58. 			this -> right = nullptr;
  59. 		}
  60.  
  61. 		void Build(Point *points, int le, int ri, int axis) {
  62. 			if(le > ri) {
  63. 				return;
  64. 			}
  65. 			else if(le == ri) {
  66. 				this -> p = points[le];
  67. 				this -> left = nullptr;
  68. 				this -> right = nullptr;
  69.  
  70. 				return;
  71. 			}
  72.  
  73. 			int mid = (le + ri) / 2;
  74. 			nth_element(points + le, points + mid, points + ri, ComparePoints(axis));
  75.  
  76. 			this -> value = points[mid].x[axis];
  77. 			this -> axis = axis;
  78.  
  79. 			this -> left = new Node();
  80. 			this -> right = new Node();
  81.  
  82. 			this -> left -> Build(points, le, mid, (axis ^ 1));
  83. 			this -> right -> Build(points, mid + 1, ri, (axis ^ 1));
  84. 		}
  85.  
  86. 		ll FindNearestNeighbour(Point qPoint) {
  87. 			if(this == nullptr) {
  88. 				return INF;
  89. 			}
  90. 			else if(this -> left == nullptr && this -> right == nullptr) {
  91. 				if(this -> p != qPoint) {
  92. 					return this -> p.CalculateDist(qPoint);
  93. 				}
  94.  
  95. 				return INF;
  96. 			}
  97.  
  98. 			ll ansLeft = INF, ansRight = INF;
  99. 			if(qPoint.x[this -> axis] <= this -> value) {
  100. 				ansLeft = this -> left -> FindNearestNeighbour(qPoint);
  101.  
  102. 				if(qPoint.x[this -> axis] + sqrt(ansLeft) >= this -> value) {
  103. 					ansRight = this -> right -> FindNearestNeighbour(qPoint);
  104. 				}
  105. 			}
  106. 			else {
  107. 				ansRight = this -> right -> FindNearestNeighbour(qPoint);
  108.  
  109. 				if(qPoint.x[this -> axis] - sqrt(ansRight) <= this -> value) {
  110. 					ansLeft = this -> left -> FindNearestNeighbour(qPoint);
  111. 				}
  112. 			}
  113.  
  114. 			return min(ansLeft, ansRight);
  115. 		}
  116. };
  117.  
  118. Node *root;
  119. Point ps[MAX_N], startPoints[MAX_N];
  120.  
  121. int main() {
  122. 	int cntTests;
  123. 	scanf(" %d", &cntTests);
  124.  
  125. 	for(int cs = 1; cs <= cntTests; cs++) {
  126. 		int n;
  127. 		scanf(" %d", &n);
  128.  
  129. 		for(int i = 0; i < n; i++) {
  130. 			scanf(" %d %d", &ps[i].x[0], &ps[i].x[1]);
  131. 			startPoints[i] = ps[i];
  132. 		}
  133.  
  134. 		root = new Node();
  135. 		root -> Build(ps, 0, n - 1, 0);
  136.  
  137. 		for(int i = 0; i < n; i++) {
  138. 			printf("%lld\n", root -> FindNearestNeighbour(startPoints[i]));
  139. 		}
  140.  
  141. 		printf("\n");
  142. 	}
  143.  
  144. 	return 0;
  145. }
  146.  
Success #stdin #stdout 0s 17648KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/fHSIaS
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!