fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. // --- GEOMETRIC STRUCTURES ---
  9.  
  10. class Rectangle {
  11. 	public:
  12.     int id;
  13.     double minX, minY, maxX, maxY;
  14.  
  15.     // The core geometric relation check
  16.     bool intersects(const Rectangle& other) const {
  17.         return !(minX > other.maxX || maxX < other.minX || 
  18.                  minY > other.maxY || maxY < other.minY);
  19.     }
  20. };
  21.  
  22. // --- PROVIDED TREE LIBRARY (Simulated with Vector) ---
  23.  
  24. class GeoTree {
  25. private:
  26.     // Internal storage simulating the Tree's dataset
  27.     vector<Rectangle> treeData;
  28.  
  29. public:
  30.     /**
  31.      * Requirement: Add operation takes O(log n) in a real tree.
  32.      * Here we use push_back for the simulation.
  33.      */
  34.     void addRectangle(int id, Rectangle r) {
  35.         r.id = id;
  36.         treeData.push_back(r);
  37.     }
  38.  
  39.     /**
  40.      * Requirement: Query operation takes O(log n) in a real tree.
  41.      * In a real library, this would only visit branches that overlap with q.
  42.      */
  43.     vector<int> queryRectangle(Rectangle q) {
  44.         vector<int> results;
  45.         for (const auto& rect : treeData) {
  46.             if (rect.intersects(q)) {
  47.                 results.push_back(rect.id);
  48.             }
  49.         }
  50.         return results;
  51.     }
  52. };
  53.  
  54. void mapCase1 (vector<Rectangle> uscities,vector<Rectangle> largeTableBPartition)
  55. {
  56. 	GeoTree geotree;
  57. 	for(auto city :uscities )
  58. 	{
  59. 		geotree.addRectangle(city.id,city);
  60. 	}
  61.  
  62. 	for(auto trip :largeTableBPartition )
  63. 	{
  64. 		vector<int> visitedCities = 	geotree.queryRectangle(trip);
  65. 		for(auto city : visitedCities )
  66. 		{
  67. 			cout<<"Intersecting cities for trip :"<<trip.id<<" are :" <<city<<"\n";
  68. 		}
  69.  
  70. 	}
  71. }
  72. int main() {
  73.     // TABLE A: Small Table (e.g., US City Boundaries)
  74.     vector<Rectangle> cities = {
  75.         {1, 0.0, 0.0, 5.0, 5.0},   
  76.         {2, 10.0, 10.0, 15.0, 15.0} 
  77.     };
  78.  
  79.     // TABLE B: Large Table Partition (e.g., Uber Trips on local node)
  80.     vector<Rectangle> trips = {
  81.         {101, 2.0, 2.0, 3.0, 3.0},   
  82.         {102, 4.0, 4.0, 6.0, 6.0},   
  83.         {103, 12.0, 12.0, 18.0, 18.0}, 
  84.         {104, 20.0, 20.0, 25.0, 25.0}  
  85.     };
  86.  
  87.     mapCase1(cities, trips);
  88.  
  89.     return 0;
  90. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Intersecting cities for trip :101 are :1
Intersecting cities for trip :102 are :1
Intersecting cities for trip :103 are :2
https://ideone.com/uRhf10
language:
C++ (gcc 8.3)
created:
21 hours 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!