/* COUNTING RECTANGLES [CODING CHALLENGE] You receive 2D coordinates of unordered points. Your task is to count how many rectangles (with vertical and horizontal sides only) are created by those points. Simple examples: [(0,0),(0,3),(1,3),(1,0),(3,0)] make 1 rectangle [(0,0),(0,3),(1,3),(1,0),(3,0),(3,3)] make 3 rectangles (squares are rectangles too) testCases: [(0,1),(0,3),(2,2),(2,3),(3,1),(3,2),(3,3),(3,4),(5,1),(5,3),(5,4)] -> 6 [(-3,-2),(-3,2),(-1,0),(-1,2),(0,0),(0,2),(0,4),(2,-3),(2,0),(2,2),(2,4),(2,7),(4,-2),(4,2),(5,-3),(5,0),(5,2),(5,4),(7,-3),(7,2),(7,7)] -> 20 from random import choices [choices(range(10000),k=2) for i in range(100000)] -> 3000 (+ or - 300) (statistical value) (that's python syntax for a choice of 100.000 random points which 2D coordinates are between 0 and 10000). Try to keep a low complexity. https://www.sololearn.com/post/216760/?ref=app */ /* COUNTING RECTANGLES [CODING CHALLENGE] You receive 2D coordinates of unordered points. Your task is to count how many rectangles (with vertical and horizontal sides only) are created by those points. Simple examples: [(0,0),(0,3),(1,3),(1,0),(3,0)] make 1 rectangle [(0,0),(0,3),(1,3),(1,0),(3,0),(3,3)] make 3 rectangles (squares are rectangles too) testCases: [(0,1),(0,3),(2,2),(2,3),(3,1),(3,2),(3,3),(3,4),(5,1),(5,3),(5,4)] -> 6 [(-3,-2),(-3,2),(-1,0),(-1,2),(0,0),(0,2),(0,4),(2,-3),(2,0),(2,2),(2,4),(2,7),(4,-2),(4,2),(5,-3),(5,0),(5,2),(5,4),(7,-3),(7,2),(7,7)] -> 20 from random import choices [choices(range(10000),k=2) for i in range(100000)] -> 3000 (+ or - 300) (statistical value) (that's python syntax for a choice of 100.000 random points which 2D coordinates are between 0 and 10000). Try to keep a low complexity. https://www.sololearn.com/post/216760/?ref=app */ /* COUNTING RECTANGLES [CODING CHALLENGE] You receive 2D coordinates of unordered points. Your task is to count how many rectangles (with vertical and horizontal sides only) are created by those points. Simple examples: [(0,0),(0,3),(1,3),(1,0),(3,0)] make 1 rectangle [(0,0),(0,3),(1,3),(1,0),(3,0),(3,3)] make 3 rectangles (squares are rectangles too) testCases: [(0,1),(0,3),(2,2),(2,3),(3,1),(3,2),(3,3),(3,4),(5,1),(5,3),(5,4)] -> 6 [(-3,-2),(-3,2),(-1,0),(-1,2),(0,0),(0,2),(0,4),(2,-3),(2,0),(2,2),(2,4),(2,7),(4,-2),(4,2),(5,-3),(5,0),(5,2),(5,4),(7,-3),(7,2),(7,7)] -> 20 from random import choices [choices(range(10000),k=2) for i in range(100000)] -> 3000 (+ or - 300) (statistical value) (that's python syntax for a choice of 100.000 random points which 2D coordinates are between 0 and 10000). Try to keep a low complexity. https://www.sololearn.com/post/216760/?ref=app */ #include #include #include #include using namespace std; auto Print = [](auto&& plist){ cout << '['; for(auto&&[px,py] : plist) cout << '(' << px << ',' << py << "),"; cout << "] => "; }; // Core function to find Rectangles auto findR = [](auto&& plist){ int nRects=0; for(auto it=plist.begin(); it!= prev(plist.end()); ++it){ for(auto it2=next(it); it2!=plist.end(); ++it2) { auto p1{*it}, p2{*it2}; auto p3 = pair{p1.first, p2.second}; auto p4 = pair{p2.first, p1.second}; if(plist.find(p3) != plist.end() && plist.find(p4) != plist.end() && (p3 != p1 && p4 != p2) && (p3 != p2 && p4 != p1)) ++nRects; } // end inner for } // end outer for Print(plist); // divide by 2 since pairs are counted twice cout << nRects/2 << "\n\n"; }; int main() { set>> plist{ {{0,0},{0,3},{1,3},{1,0},{3,0},{3,3}}, {{0,1},{0,3},{2,2},{2,3},{3,1},{3,2},{3,3}, {3,4},{5,1},{5,3},{5,4}}, {{-3,-2},{-3,2},{-1,0},{-1,2},{0,0},{0,2}, {0,4}, {2,-3},{2,0}, {2,2}, {2,4},{2,7}, {4,-2}, {4,2}, {5,-3},{5,0}, {5,2},{5,4}, {7,-3}, {7,2}, {7,7}}, {{7,1},{3,5},{3,1},{1,5},{1,1},{7,5}}, {{3,10},{3,8},{3,6},{3,4},{3,0},{6,0}, {6,4}, {6,8},{6,10}}, {{17,2}, {6,19}, {10,29},{18,19},{27,27}, {9,4}, {22,24},{25,1}, {19,15},{28,28}, {1,16}, {11,6}, {14,13},{24,6}, {4,12}, {30,3}, {14,4}, {22,18},{16,25},{3,4}, {28,20},{19,5}, {12,9}, {6,0}, {28,4}, {18,27},{7,8}, {0,30}, {9,17}, {0,5},{23,12},{26,16},{13,31},{9,1},{11,27},{15,10},{15,23},{30,6},{16,22},{5,17},{6,24},{7,19},{25,21},{15,24},{13,30},{15,11},{31,21},{10,2},{27,18},{20,16},{19,26},{3,31},{19,29},{19,27},{14,30},{26,1},{28,11},{30,30},{4,15},{25,19},{17,31},{16,3},{5,31},{0,18},{5,2},{27,29},{0,10},{0,14},{8,3},{27,7},{4,5},{27,11},{15,12},{30,12},{16,30},{9,0},{27,15},{19,11},{6,1},{22,29},{5,19},{31,1},{12,12},{27,31},{0,0},{17,20},{22,22},{21,22},{10,23},{29,24}}, {{3,1},{7,5},{4,5},{2,6},{2,0},{7,4},{2,4},{2,1},{7,0},{6,4},{6,7},{5,1},{0,1},{1,5},{4,0},{7,7},{2,5},{0,0},{5,2},{4,7},{5,6},{7,6},{7,3},{6,5},{5,3},{6,6},{7,1},{6,1},{1,2},{4,4},{2,3},{3,7},{0,3},{3,3},{4,2},{0,6},{5,0},{2,7},{1,4},{2,2},{3,4},{5,4},{5,7},{1,0},{0,7},{1,1},{6,0},{0,4},{7,2},{5,5},{0,2},{0,5},{3,6},{4,1},{3,2},{4,3},{6,2},{4,6},{1,3},{3,5},{3,0}}, {{0,0},{0,1},{0,2},{0,3},{0,4},{0,5},{0,6},{0,7},{1,0},{1,1},{1,2},{1,3},{1,4},{1,5},{1,6},{1,7},{2,0},{2,1},{2,2},{2,3},{2,4},{2,5},{2,6},{2,7},{3,0},{3,1},{3,2},{3,3},{3,4},{3,5},{3,6},{3,7},{4,0},{4,1},{4,2},{4,3},{4,4},{4,5},{4,6},{4,7},{5,0},{5,1},{5,2},{5,3},{5,4},{5,5},{5,6},{5,7},{6,0},{6,1},{6,2},{6,3},{6,4},{6,5},{6,6},{6,7},{7,0},{7,1},{7,2},{7,3},{7,4},{7,5},{7,6},{7,7}} }; for(auto&& ts : plist) findR(ts); }

[Challenge] Find_max_rectangles.cpp