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!