Thread: Maximum Possible Rectangles

  1. #16
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    102
    Hey!

    Flp's interpretation is wrong.

    Let's say there are four points with their coordinates entered (A, B, C, D be the points). Based on the rectangle posted by flp, AB forms one side of the rectangle (with A and B forming a line segment, A being one vertice and B being the other). Till here, he's correct. But this rectangle isn't to be considered as one side of the rectangle merely passes through a given point C, and does not have C as a vertex.
    If A, B, C, D are the given points then ABCD should be a rectangle formed and that must be counted, not any other rectangle that has a side passing through 3(or)2(or)1 of the given points.

    https://cboard.cprogramming.com/atta...s-untitled-png

    > So do the lines that from the rectangles have to be aligned with the axis?

    No, not necessarily. Example 3 in #13 is not aligned with the axes. Yet, the rectangle formed by them is counted because the set of points entered serve as vertices. In flp's interpretation (the diagram he provided us with), one of the side passes through C, but does not have C as a vertex point, so such rectangles are not to be counted. Only those that can be formed using four points from the set of points such that the four points are the vertices of the rectangle.

    > and both will give very different answers

    Yes, that's true. But I think I've made myself clear now. The three example inputs should make it clear too.

    Thanks!

    @flp, if there's been any misunderstanding/miscommunication between the two of us, I apologise for that. I think it's become clear what I've been intending to convey. Thanks!

  2. #17
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    102
    The question says to find the maximum possible number of rectangles. But it would be interesting to add code for displaying the points that form each rectangle.

  3. #18
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    102
    I found a similar question but this one caters to only those rectangles whose edges/sides are parallel to axes. This is fairly easier question in which I didn't have to find slopes and do all the stuff I'm doing in my code above. I have an O(N^2) solution to it but I'll work on finding a more optimum solution, if any.

    Contest Page | CodeChef

  4. #19
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,456
    Quote Originally Posted by Zeus_ View Post
    I found a similar question but this one caters to only those rectangles whose edges/sides are parallel to axes. This is fairly easier question in which I didn't have to find slopes and do all the stuff I'm doing in my code above. I have an O(N^2) solution to it but I'll work on finding a more optimum solution, if any.

    Contest Page | CodeChef
    Well, it's not a new problem. E.g. it is discussed by: Kreveld & Berg (1989) (https://pure.tue.nl/ws/files/4288742/369233.pdf); Bereg, Mutsanas & Wolff (2009) and in books dealing with computational geometry.

    The main "problem" I have with your solution (apart from being suboptimal) is the comparison of floating point numbers, but you've acknowledged this limitation

    Edit: Given points on a plane like ( | CareerCup may be useful to review as well
    Last edited by Hodor; 10-02-2019 at 02:24 AM.

  5. #20
    Registered User
    Join Date
    Feb 2019
    Posts
    533
    Quote Originally Posted by Zeus_ View Post
    Hey!

    Flp's interpretation is wrong.

    Let's say there are four points with their coordinates entered (A, B, C, D be the points). Based on the rectangle posted by flp, AB forms one side of the rectangle (with A and B forming a line segment, A being one vertice and B being the other). Till here, he's correct. But this rectangle isn't to be considered as one side of the rectangle merely passes through a given point C, and does not have C as a vertex.
    My point was that the question isn't clear enough about this, since "corner" is a generic term, instead of "vertice". Put point C close to one of the oposite vertices and it is "at the corner", as in a boxing ring or "the corner of a room". This interpretation allows for rectangles as in that figure.

    NOW it is clear all ponts that can form a rectangle (3 or 4 - not 2, which will give us infinite rectangles [with different areas and alignment]) must be AT the vertices. Is that correct and sufficient?
    Quote Originally Posted by Zeus_ View Post
    Hey!@flp, if there's been any misunderstanding/miscommunication between the two of us, I apologise for that. I think it's become clear what I've been intending to convey. Thanks!
    Nah! That's all right! I apologize as well

    I'm thinking about (maybe it is not a good idea - more calculations!) using vectors to solve the problem. Maybe it is easier to use dot products to test for parallelism and "perpendicularism"... For perpendicular vectors there's no need for divisions, since cos(PI/2)=0, for instance.

  6. #21
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    102
    > NOW it is clear all ponts that can form a rectangle (3 or 4 - not 2, which will give us infinite rectangles [with different areas and alignment]) must be AT the vertices. Is that correct and sufficient?

    Yes, the points that from a rectangle must be its vertices.

    On another note, if only 2 points and their coordinates are entered, the result of total possible rectangle should be zero (not infinite, like you said) because as mentioned above, the entered points must be the vertices of the rectangle formed, if any, and we need a minimum of 4 points for the rect to be formed. So, for input of points like 1, 2, 3, the result of rectangles is 0. This is taken care of because as mentioned in the question paper (and later in one of my posts) the constraints of the problem are 4 < Points < 100.

    >
    I'm thinking about (maybe it is not a good idea - more calculations!) using vectors to solve the problem. Maybe it is easier to use dot products to test for parallelism and "perpendicularism"... For perpendicular vectors there's no need for divisions, since cos(PI/2)=0, for instance.

    Yes, that's what I was doing right now. Instead of calculating slopes by doing (y2 - y1)/(x2-x1), if the dot product is 0, then the lines are perpendicular and if the cross product is 0, the lines are parallel. This takes care of one of the inherent issues i.e. the floating point if-checks.
    Thanks!

  7. #22
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    102
    Thanks for referring me the docs, I've downloaded the PDF and will make sure to read through carefully. For now though, I will not be reading through any solutions as that way I don't get to strain my brain. As I mentioned I'm practicing for a competitive programming event that's coming up so I wanna be able to finish what I start implementing before I look at other solutions (unless, I figure out that the entire logic is flawed). Obviously, the code I attached in #1 isn't going to work because of the inherent issues.


    > The main "problem" I have with your solution (apart from being suboptimal) is the comparison of floating point numbers, but you've acknowledged this limitation


    Is there a way I can do floating point comparisons my estimating/rounding them and get accurate results? If so, please do mention them.

  8. #23
    Registered User
    Join Date
    Aug 2019
    Location
    Inside a Singularity
    Posts
    102
    Code:
    #include <iostream>
    
    
    struct Point
    {
        int x;
        int y;
    
    
        Point () : x(0) , y(0) { }
    };
    
    
    class Line
    {
    private:
    
    
        int _X;
        int _Y;
    
    
    public:
    
    
        Line () : _X(0) , _Y(0) { }
    
    
    public:
    
    
        void MakeLineVector (int& x1, int& y1, int& x2, int& y2);
        int  DotProduct     (Line& _line)                       ;
        int  CrossProduct   (Line& _line)                       ;
    
    
    public:
    
    
        int  GetX (void) { return _X; }
        int  GetY (void) { return _Y; }
    };
    
    
    void Line::MakeLineVector (int& x1, int& y1, int& x2, int& y2)
    {
        _X = x2 - x1;
        _Y = y2 - y1;
    }
    
    
    int Line::DotProduct   (Line& _line) { return ((_X * _line._X) + (_Y * _line._Y)); }
    
    
    int Line::CrossProduct (Line& _line) { return ((_X * _line._Y) - (_Y * _line._X)); }
    
    
    int main (void)
    {
        int TotalPoints , Ctr1 , Ctr2 , Ctr3 , Ctr4;
    
    
        std::cout << std::endl
                  << "Enter Number of Points: ";
    
    
        std::cin >> TotalPoints;
    
    
        Point* Coordinate = new Point[TotalPoints];
    
    
        for (Ctr1 = 0; Ctr1 < TotalPoints; Ctr1++)
        {
            std::cout << "Point " << Ctr1 + 1 << " x: "; std::cin >> Coordinate[Ctr1].x;
            std::cout << "Point " << Ctr1 + 1 << " y: "; std::cin >> Coordinate[Ctr1].y;
        }
    
    
        int TotalPossibleLines = ((TotalPoints)*(TotalPoints - 1)) / 2 , CurrentLine = 0;
    
    
        Line* Vector = new Line[TotalPossibleLines];
    
    
        for (Ctr1 = 0; Ctr1 < TotalPoints - 1; Ctr1++)
        {
            for (Ctr2 = Ctr1 + 1; Ctr2 < TotalPoints; Ctr2++)
            {
                Vector[CurrentLine].MakeLineVector(Coordinate[Ctr1].x, Coordinate[Ctr1].y, Coordinate[Ctr2].x, Coordinate[Ctr2].y);
    
    
                CurrentLine++;
            }
        }
    
    
        int TotalPossibleRectangles = 0;
    
    
        for (Ctr1 = 0; Ctr1 < TotalPossibleLines; Ctr1++)
        
            for (Ctr2 = Ctr1 + 1; Ctr2 < TotalPossibleLines; Ctr2++)
    
    
                if (Vector[Ctr1].CrossProduct(Vector[Ctr2]) == 0) // Parallel lines
    
    
                    for (Ctr3 = 0; Ctr3 < TotalPossibleLines; Ctr3++)
    
    
                        if (Vector[Ctr3].DotProduct(Vector[Ctr1 /*or Ctr2*/]) == 0) // Perpendicular lines
    
    
                            for (Ctr4 = Ctr3 + 1; Ctr4 < TotalPossibleLines; Ctr4++)
                            
                                if (Vector[Ctr3].CrossProduct(Vector[Ctr4]) == 0) // Parallel lines
    
    
                                    TotalPossibleRectangles++;
    
    
        std::cout << std::endl << "Total Rectangles: " << TotalPossibleRectangles;
    
    
    
    
        for(Ctr1 = 0; Ctr1 < TotalPossibleLines; Ctr1++)
        {
            std::cout << std::endl << " (" << Vector[Ctr1].GetX() << ")i + (" <<  Vector[Ctr1].GetY() << ")j";
        }
    
    
    
    
        delete[] Vector;
        delete[] Coordinate;
    
    
        return 0;
    }
    Hey, I got rid of the slope approach as Dot and Cross Products are easier to handle, something which should've been my first thought but I realised how stupid I was being by calculating the slope this morning. (Credit to @flp too as he commented about using the same a few hours after I realised my stupidity).

    Note: This program isn't working like I expected it too and I'm not in a state of mind to find what's wrong as it's been a tiring day. I'll sort it out after school tomorrow but until then if someone does decide to run the code and looks at what's going on, please do tell me.
    It's nothing different from the previous code. Just a better way to decide if a line is parallel or perpendicular.

    I'm guessing each rectangle is being counted more than once proportional to the number on points being entered. I can simply divide it by the proportion constant (if I'm able to figure it out) and get a working solution but that wouldn't be what I'll be doing. First thing after school tomorrow, I'm gonna sit and find where I'm going wrong.

    Thanks for the help provided by everybody!

    (PS: Sorry about the code elongation. Whenever I copy-paste code, each newline character in my code is translated to two newlines on her idk why)

  9. #24
    Registered User
    Join Date
    Oct 2019
    Posts
    1
    tnx hodor This is my question too
    Do you just have to find the number of rectangles? !!
    طراحی سایت در تهران
    طراحی سایت شرکتی
    Last edited by criswizard; 3 Weeks Ago at 03:07 AM.

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