fork(15) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. struct building {
  6. 	int l;		
  7. 	int h;		 
  8. 	int r;		
  9. };
  10. struct skyline {
  11. 	int x;
  12. 	int h;
  13. };
  14. void mergeSkylines ( auto &left, auto &right, auto &s ) {
  15.  
  16. 	int i = 0, j = 0, h1 = 0, h2 = 0, h = 0;
  17. 	while ( i < left.size() && j < right.size() ) {
  18. 		if ( left[i].x < right[j].x ) {
  19. 			h1 = left[i].h;
  20. 			if ( max(h1, h2) != h ) {
  21. 				h = max(h1, h2);
  22. 				s.push_back ({left[i].x, h});
  23. 			}
  24. 			i++;
  25. 		}
  26. 		else {
  27. 			h2 = right[j].h;
  28. 			if ( max(h1, h2) != h ) {
  29. 				h = max (h1, h2);
  30. 				s.push_back ({right[j].x, h});
  31. 			}
  32. 			j++;
  33. 		}
  34. 	}
  35. 	while ( i < left.size() ) {
  36. 		if ( left[i].h != h ) {
  37. 			h = left[i].h;
  38. 			s.push_back ({left[i].x, h});
  39. 		}
  40. 		i++;
  41. 	}
  42.  
  43. 	while ( j < right.size() ) {
  44. 		if ( right[j].h != h ) {
  45. 			h = right[j].h;
  46. 			s.push_back ({right[j].x, h});
  47. 		}
  48. 		j++;
  49. 	}
  50. }
  51. void formSkyline ( auto &b, int l, int r, auto &s ) {
  52. 	if ( l == r ) {
  53. 		// base case 
  54. 		s.push_back ({b[l].l, b[l].h});
  55. 		s.push_back ({b[l].r, 0});
  56. 	}
  57. 	else if ( l < r ) {
  58. 		int mid = (l + r) / 2;
  59. 		vector<skyline> left, right;
  60. 		formSkyline ( b, l, mid, left );
  61. 		formSkyline ( b, mid + 1, r, right );
  62. 		mergeSkylines ( left, right, s );
  63. 	}
  64. }
  65. int main ( ) {
  66.  
  67. 	//vector<building> b = {{1, 5, 4}, {2, 6, 3}};
  68. 	vector<building> b = { {1,11,5}, {2,6,7}, {3,13,9}, {12,7,16}, {14,3,25}, {19,18,22}, {23,13,29}, {24,4,28} };
  69.    vector<skyline> s;
  70.    formSkyline ( b, 0, b.size() - 1, s );
  71.    cout << "Resulting Skyline : \n";
  72.    for ( auto i : s ) 
  73.    	cout << "[" << i.x << " " << i.h << "] ";
  74. 	return 0;
  75. }
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Resulting Skyline : 
[1 11] [3 13] [9 0] [12 7] [16 3] [19 18] [22 3] [23 13] [29 0]
https://ideone.com/tP0aIo
language:
C++14 (gcc 8.3)
created:
8 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!