Thread: Maximum Possible Rectangles

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!

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.

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

Originally Posted by Zeus_

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?

Originally Posted by Zeus_

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.

> 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!

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.

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)