1. ## 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.

Thanks for your help, time, and patience!  2. 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. 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). 4. 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. 5. 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. 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. Originally Posted by Zeus_ 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?

[ 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. 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. Originally Posted by Zeus_ 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"): 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... 10. 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. 11. You're just being stupid. I'm not gonna bother replying to the crap you post. 12. 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. 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. 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. 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 coordinates, ctr1, int, number, point 