fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <climits>
  6.  
  7. using namespace std;
  8.  
  9. struct Point {
  10.     int x, y, idx;
  11. };
  12.  
  13. int manhattan(const Point& a, const Point& b) {
  14.     return abs(a.x - b.x) + abs(a.y - b.y);
  15. }
  16.  
  17. enum ProjectionType {
  18.     XY,
  19.     X_Y,
  20.     _XY,
  21.     _X_Y
  22. };
  23.  
  24. int project(const Point& p, ProjectionType type) {
  25.     if (type == XY) return p.x + p.y;
  26.     if (type == X_Y) return p.x - p.y;
  27.     if (type == _XY) return -p.x + p.y;
  28.     return -p.x - p.y;
  29. }
  30.  
  31. void check(vector<int>& result, vector<int>& dist, vector<Point> points, ProjectionType projType) {
  32.     sort(points.begin(), points.end(), [projType](const Point& a, const Point& b) {
  33.         return project(a, projType) < project(b, projType);
  34.     });
  35.  
  36.     int n = points.size();
  37.     for (int i = 0; i < n; ++i) {
  38.         int idx = points[i].idx;
  39.         for (int j = -1; j <= 1; j += 2) {
  40.             int k = i + j;
  41.             if (k < 0 || k >= n) continue;
  42.             int d = manhattan(points[i], points[k]);
  43.             if (d < dist[idx] || (d == dist[idx] && points[k].idx < result[idx])) {
  44.                 dist[idx] = d;
  45.                 result[idx] = points[k].idx;
  46.             }
  47.         }
  48.     }
  49. }
  50.  
  51. int main() {
  52.     int n;
  53.     cin >> n;
  54.     vector<Point> points(n);
  55.     vector<int> result(n, -1);
  56.     vector<int> dist(n, INT_MAX);
  57.  
  58.     for (int i = 0; i < n; ++i) {
  59.         cin >> points[i].x >> points[i].y;
  60.         points[i].idx = i;
  61.     }
  62.  
  63.     check(result, dist, points, XY);
  64.     check(result, dist, points, X_Y);
  65.     check(result, dist, points, _XY);
  66.     check(result, dist, points, _X_Y);
  67.  
  68.     for (int i = 0; i < n; ++i) {
  69.         cout << (result[i] + 1) << " ";
  70.     }
  71.     cout << endl;
  72.     return 0;
  73. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/6KsbFa
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
1 day 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!