Thread: Maximum Possible Rectangles

  1. #1
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308

    Maximum Possible Rectangles

    Hey, I've been practicing for another competitive programming event and there's this question which I'm facing difficulty solving.

    So, the question is to count the number of all possible rectangles that are formed on the x-y plane given the coordinates of a variable number of points. It is also given that no two coordinates of a point will be the same as the coordinates of any other point.

    Here's my try:

    Code:
    #include <iostream>
    
    
    struct Point
    {
        int x;
        int y;
    };
    
    
    int main (void)
    {
        int TotalPoints , Ctr1 , Ctr2 , Ctr3 , Ctr4;
    
    
        std::cout << std::endl
                  << "Enter Number of Points: ";
    
    
        std::cin >> TotalPoints;
    
    
        Point* Coordinates = new Point[TotalPoints];
    
    
        for (Ctr1 = 0; Ctr1 < TotalPoints; Ctr1++)
        {
            std::cout << "Point " << Ctr1 + 1 << " x: "; std::cin >> Coordinates[Ctr1].x;
            std::cout << "Point " << Ctr1 + 1 << " y: "; std::cin >> Coordinates[Ctr1].y;
        }
    
    
        int TotalPossibleLines = ((TotalPoints)*(TotalPoints - 1)) / 2 , Line = 0;
    
    
        float* SlopeOfLine = new float[TotalPossibleLines] { 0.0f };
        //float* SlopeOfPerpendicularLine = new float[TotalPossibleLines] { 0.0f };
    
    
        for (Ctr1 = 0; Ctr1 < TotalPoints - 1; Ctr1++)
        {
            for (Ctr2 = Ctr1 + 1; Ctr2 < TotalPoints; Ctr2++)
            {
                SlopeOfLine[Line] = (float)((float)(Coordinates[Ctr2].y - Coordinates[Ctr1].y) / (float)(Coordinates[Ctr2].x - Coordinates[Ctr1].x));
    
    
                //SlopeOfPerpendicularLine[Line] = -(1.0f / SlopeOfLine[Line]);
    
    
                Line++;
            }
        }
    
    
        /*for (Ctr1 = 0; Ctr1 < TotalPossibleLines; Ctr1++)
        {
            std::cout << std::endl << SlopeOfLine[Ctr1]; // " " << SlopeOfPerpendicularLine[Ctr1] << std::endl;
        }*/
    
    
        int TotalRectangles = 0;
    
    
        for (Ctr1 = 0; Ctr1 < TotalPossibleLines; Ctr1++)
        {
            for (Ctr2 = Ctr1 + 1; Ctr2 < TotalPossibleLines; Ctr2++)
            {
                if (SlopeOfLine[Ctr1] == SlopeOfLine[Ctr2])
                {
                    for (Ctr3 = 0; Ctr3 < TotalPossibleLines; Ctr3++)
                    {
                        if (SlopeOfLine[Ctr3] * SlopeOfLine[Ctr1 /*or Ctr2*/ ] == -1)
                        {
                            for (Ctr4 = Ctr3 + 1; Ctr4 < TotalPossibleLines; Ctr4++)
                            {
                                if (SlopeOfLine[Ctr3] == SlopeOfLine[Ctr4])
                                    TotalRectangles++;
                            }
    
    
                        }
                    }
                }
            }
        }
    
    
        std::cout << std::endl << "Total Possible Rectangles: " << TotalRectangles;
    
    
        delete[] SlopeOfLine;
        //delete[] SlopeOfPerpendicularLine;
        delete[] Coordinates;
    
    
        return 0;
    }
    (Note: I meant to write the pseudo-code first and then try to use modern C++ containers to do the same thing I've done above. However, I lack practice with vectors, maps, etc. So, if someone can help me with learning the modern C++ way of writing the same code, I'm down for it)

    What I'm trying to do in the above code?

    From a mathematical viewpoint, I think my logic makes sense but there are certain problems that I'm having whilst converting my logic to code.
    So, what I'm trying to do is this:
    - Take in a set of points and their coordinates
    - Find all possible slope of lines through each pair of points
    (If there are 4 points, then total possible lines are 6 which can be easily found out by using the formula (n*(n-1))/2 )
    - Loop through all possible slopes and search for any two same slope values. These indicate parallel lines (Note: They may indicate the same line but that wouldn't happen as it is given that no two coordinates of a point will be the same as that of any other point)
    - Once I find a set of parallel lines, I start looping through the slopes of all possible lines again and search for a slope such that the value of the slope found in the above point times the value of slopes currently being looped is equal to -1.
    (Why? Because the product of slopes of two lines = -1 (m1 * m2 = -1 ) )
    - Once I find any such line/slope such that it is indeed perpendicular, I start looking for another slope with the same slope value (as that of the perpendicular) because I'll need two perpendicular lines to form the rectangle.
    - If all conditions are met, I get one rectangle. Similarly, once all possible conditions are exhausted, I'll get my total number of rectangles.

    Now, obviously I'm going to be criticised for this approach because it makes for a very dirty code and there might be better approaches on the internet for solving the same problem but this was my own logic that I came up with, so, I wanna stick with this and get to the bottom of the inherent issues before looking at other approaches.

    Inherent issues:

    1)
    There might be a situation where the slope of a line is positive infinity (or negative infinity) i.e. (1/0) (or (-1/0) ) and the slope of another line is 0. It is obvious that the two lines are perpendicular but going by what I implemented, we can never have the condition of the product of slopes being equal to -1 because,
    Logically, (and Mathematically) ((-1/0)*0 = -1 ) (Not saying that 0 and 0 cancel each other out but that's how we know the two will be perpendicular. But this is not the result that the computer will give. I'm writing my program in C::B and compiling with GNU GCC so I can use negative infinity and positive infinity and as a matter of fact, if I choose to display the slopes, it gives me the correct results like so "-inf" for negative infinity and "inf" for positive infinity.
    Is there a way I can get through this without having to do error checking (i.e. divide by zero)? I think that I can add more check conditions and based upon it modify the product of slopes result.

    2)
    For floating point numbers, 0.666... * -1.5 = -0.999...
    So, if I have two slopes which are actually perpendicular, I'm getting a result -0.999... which is -1, but doing the comparison -0.999... == -1 results in a false statement. Is there a way I can doing floating point comparisons for numbers that are very close to each other? Is there a way I can round my number to the nearest decimal point? This way, a rounded up -0.999... will give -1.

    ---------------------

    Again, I know the code is very flawed for the inherent issues that are there but speaking from a mathematical viewpoint, I think the logic makes sense but having to implement it in code is something rather difficult as taking care of these pesky and minute bugs is a difficult.

    Please redirect me to reading material on the problem, if any.

    Thanks for your help, time, and patience!

  2. #2
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    Sorry for the code elongation. Every time I copy-paste code from C::B, each newline character results in two newline characters on here. So, the program looks bigger than it actually is.

  3. #3
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    I would criticize this approach not because of the code, but because lacks the rigorous definition of what would constitute a rectangle based on the points diven... With 3 points you can draw, at least, 12 rectangles (not only orthogonal ones which uses 2 points, but inner rectangles, one outer orthogonal rectangle and 3 non-orthogonal ones - use pen, paper and a set-square and you'll see).
    Last edited by flp1969; 09-30-2019 at 09:56 AM.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Code:
        for (Ctr1 = 0; Ctr1 < TotalPossibleLines; Ctr1++)
        {
            for (Ctr2 = Ctr1 + 1; Ctr2 < TotalPossibleLines; Ctr2++)
            {
                if (SlopeOfLine[Ctr1] == SlopeOfLine[Ctr2])
                {
                    for (Ctr3 = 0; Ctr3 < TotalPossibleLines; Ctr3++)
                    {
                        if (SlopeOfLine[Ctr3] * SlopeOfLine[Ctr1 /*or Ctr2*/ ] == -1)
                        {
                            for (Ctr4 = Ctr3 + 1; Ctr4 < TotalPossibleLines; Ctr4++)
    You don't solve these problems by brute force.

    They're mostly solved on paper by you coming up with a really clever algorithm that works for very large values of N.
    IE the values of N that the automated test throws at you which expose all the simple implementations with either "too much memory" or "too much time" errors.

    > Please redirect me to reading material on the problem, if any.
    Books and websites which tell you all about planar geometry would be a good bet.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    Buddy, read the question again. In case it's not very clear, a rectangle is a shape with a pair of sides parallel to each other and another pair of sides that are also parallel but perpendicular to the previous pair of lines. And also, the corners of the rectangle should be on the given points, not any line that merely passes through the point giving rise to not 12 but an infinite number of rectangles. I didn't mention it in my post because I thought it was understood as a matter of fact but now I need to do that.

    Count the number of all possible rectangles formed given a set of points and their coordinates in the X-Y plane. The rectangles must have their corners at the given points, if any. No two points will have the same coordinates.

    I think this makes it clear.

  6. #6
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    Hey Salem! Again, I implemented this because this was the first idea I got after looking at the question. The constraint mentioned in the question was 4 < No. of points < 100. I stuck with arrays as I felt 100 was a small size, but again, what you're saying is correct. I don't know much about time complexity but I guess for four nested for loops (without my if checks, etc), the time complexity is O(N^4) which is really bad. For the current program that I'm implementing, I think I can reduce it to O(N^3), as once I have a pair of parallel lines (let's call them A and B), I can loop through the other slopes and find one such that the product of slopes equals -1 (If an such line exists, then lets call the third point C). Then, a simple check to find a point D can be done such that D = B + C - A (I understood this by using the vector form of all points, the vector being the position vector). Therefore, if such a point D exists in the entered set of points and their coordinates, I have a rectangle.

    I was at the school library earlier today and was going through a few math textbooks on Geometry but I didn't find anything that I haven't already thought of. It's my last year at school and math is my best subject so there's not much in the school library textbooks that I didn't know already. I'll have to read and do some research from higher level books maybe to think of other ways.

    (I don't know how time complexity is calculated so I might be wrong but from the little bit that I've come across, I made a mention of it)

    Thanks!

  7. #7
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    Quote Originally Posted by Zeus_ View Post
    Buddy, read the question again. In case it's not very clear, a rectangle is a shape with a pair of sides parallel to each other and another pair of sides that are also parallel but perpendicular to the previous pair of lines
    WoW! Really... don't tell me, it has 4 sides as well?

    [
    Quote Originally Posted by Zeus_
    And also, the corners of the rectangle should be on the given points, not any line that merely passes through the point giving rise to not 12 but an infinite number of rectangles. I didn't mention it in my post because I thought it was understood as a matter of fact but now I need to do that.

    Count the number of all possible rectangles formed given a set of points and their coordinates in the X-Y plane. The rectangles must have their corners at the given points, if any. No two points will have the same coordinates.

    I think this makes it clear.
    Not really... by "corner" you mean the rectangle vertices or its sides? These vertices must be opposing or they can be at the same "side"?
    BE SPECIFIC!

  8. #8
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    My eyes bleed reading this.

    > BE SPECIFIC!

    I'm not the one who's supposed to be specific. That is literally what the question is. Any (non-idiotic, I may add) person will understand the question. Seriously, I shouldn't be explaining what a damn corner is, it's common sense. The side of a rectangle is not called a corner. It's called an EDGE. A vertice is a corner point, or more specifically, a corner-point is the point where a curve intersects another curve. Lines are curves. Two lines perpendicular to each other intersect. Thus, they have a corner-point which is the intersection point. The rectangle is formed by 4 such corner-points/vertices which are intersections of perpendicular lines.

    > by "corner" you mean the rectangle vertices or its sides?

    I think you'll understand now. A side is an edge. Vertices are corners.

    Edge (geometry) - Wikipedia

  9. #9
    Registered User
    Join Date
    Feb 2019
    Posts
    1,078
    Quote Originally Posted by Zeus_ View Post
    I'm not the one who's supposed to be specific. That is literally what the question is. Any (non-idiotic, I may add) person will understand the question. Seriously, I shouldn't be explaining what a damn corner is, it's common sense. The side of a rectangle is not called a corner. It's called an EDGE. A vertice is a corner point, or more specifically, a corner-point is the point where a curve intersects another curve. Lines are curves. Two lines perpendicular to each other intersect. Thus, they have a corner-point which is the intersection point. The rectangle is formed by 4 such corner-points/vertices which are intersections of perpendicular lines.
    Interesting... I never thought about rectangles to have 4 "corners"/vertices and with perpendicular edges/sides... this is so new to me!

    By your criteria, the maximum number of rectangles when you have 2 or more than 4 points is NONE, always, because (quoting your text):

    Count the number of all possible rectangles formed given a set of points and their coordinates in the X-Y plane. The rectangles must have their corners at the given points, if any. No two points will have the same coordinates
    With 3 or 4 points you only have ONE rectangle if they form perpendicular lines, by this "definition".

    If you aren't so illiterate in geometry, you could get that you can do this, as well (lines ARE parallel, opposite sides are equal) -- This what I called "non orthotogonal" rectangle (which is, of course, a misnomer, it should be an "non orthogonally ALIGNED rectangle"):

    Maximum Possible Rectangles-untitled-png

    A "corner" is a general area around a vertice, not a vertice per se... it is NOT a precise term. Think about all those times you were at the corner of the classroom, using that funny conical hat...
    Last edited by flp1969; 10-01-2019 at 05:27 AM.

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    It would help if you provided some actual inputs we could test with, along with your interpretation of what the correct answer should be.

    And your analysis in post #6 is essentially correct, your initial code is basically O(N4). This is bad, because your solution doesn't scale very well at all.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  11. #11
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    You're just being stupid. I'm not gonna bother replying to the crap you post.

  12. #12
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    Example 1:

    Points: 6

    Coordinates: (0,0) , (0,1) , (1,0) , (1,1) , (2,0) , (2,1)

    Total Possible Rectangles: 3 (Two smaller ones and one larger one)

    1) (0,0) , (0,1) , (1,1) , (1,0) Smaller one
    2) (1,0) , (1,1) , (2,1) , (2,0) Smaller one
    3) (0,0) , (0,1) , (2,1) , (2,0) Larger one

    Example 2:

    Points: 7

    Coordinates: (0,0) , (1,1) , (2,2) , (3,3) , (4,2) , (5,1) , (6,0)

    Total Possible Rectangles: 0

    Example 3:

    Points: 4

    Coordinates: (1,1) , (2,0) , (3,1) , (2,2)

    Total Possible Rectangles: 1

  13. #13
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    Code:
    for (Ctr1 = 0; Ctr1 < TotalPossibleLines; Ctr1++)
    {
        for (Ctr2 = Ctr1 + 1; Ctr2 < TotalPossibleLines; Ctr2++)
        {
            if (SlopeOfLine[Ctr1] == SlopeOfLine[Ctr2])
            {
                for (Ctr3 = 0; Ctr3 < TotalPossibleLines; Ctr3++)
                {
                    if (SlopeOfLine[Ctr3] * SlopeOfLine[Ctr1 /*or Ctr2*/ ] == -1)
                    {
                        for (Ctr4 = Ctr3 + 1; Ctr4 < TotalPossibleLines; Ctr4++)
    Hey, wouldn't it be O(N^4) when all of the four loops use N elements? I haven't learnt about time complexity yet and the only info I know about it is from superficial reading so I may be wrong but in my code, certain loops run only when certain conditions are met i.e. it will be true O(N^4) when all points form rectangles wrt 3 other points in the set of points. The worst case scenario is when no rectangles are formed making it just O(N^3)-ish of just looping through I guess. Could you explain to me if that's correct? I know my code is just a brute force approach, as you said, but learning a little bit about something (time complexity, here) is better than having nothing to learn at all from this solution.
    Also, if no parallel lines are formed (which is tested in the first two for loops), the if condition is never met. So, does this make the time complexity of just looping through O(N^2)?

  14. #14
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    So do the lines that form the rectangles have to be aligned with the axis? Or can they be "rotated" as in flp1969's example? Because both are valid interpretations of the problem as you've stated it, and both will give very different answers

  15. #15
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,791
    The other question I have is: do you have to actually find the rectangles or just answer the question "what is the maximum possible number of rectangles"?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. drawing and filling rectangles [gtk+]
    By pink666 in forum C++ Programming
    Replies: 1
    Last Post: 05-06-2010, 03:06 PM
  2. GDI Rectangles
    By Darklighter in forum Windows Programming
    Replies: 3
    Last Post: 10-16-2006, 02:46 AM
  3. drawing lines and rectangles in c++
    By thestien in forum C++ Programming
    Replies: 41
    Last Post: 10-08-2006, 07:43 AM
  4. Difference Of Rectangles
    By SMurf in forum C Programming
    Replies: 2
    Last Post: 09-14-2005, 01:12 PM
  5. array of rectangles
    By xlnk in forum Windows Programming
    Replies: 5
    Last Post: 12-18-2002, 07:32 PM

Tags for this Thread