leochen40505
BAN USERspecial case: lines of rectangles may not always be horizontal or vertical. e.g. (0, 0), (1, 2), (3, 4), (4, 2)
assumption: set of points are store in a hashed table. let's call it pointsSet
solution steps:
1. select any point
2. iterate through the rest of the points. O(n)
3. for each points in step 2, calculate the slope of the 2 points from step 1 and 2. using the slope(double, x/y) as key, store the point from step 2 into a hash table(let's call it slopeSet) and check if there's a tangent slope exists from previous points(by checking positive and negative of the inverse slope. if slope is represented as x/y, then check for y/x and y/x)
4. if a previous slope is found in the slopeSet. use the 3 points to check if the fourth point exists in pointsSet(by calculating x and y displacements of the 3 points to get the fourth point). if it does compare the area with the current smallest area store in a variable(initialized as 1. if the value is 1 then replace the value with current area. else compare the area)
5. remove the point selected in step 1. and start from step 1 again until all points are compared. return smallest area. if 1 is returned then it means there's no rectangle formed from the points. O(n)
Performance evaluation:
O(n^2) since there are 2 for loops with O(n)
c++ solution
use an array as index of a multibase on different digit number
vector<int> dimension = getDim();
//subtract 1 from every dimension to use as index
for (int idx = 0; idx < dimension.size(); idx++) {
dimension[idx];
}
//use as the array of index pass to getElement
vector<int> idxV = dimension;
long retSum = 0;
while(true) {
int idx = 0;
//update index array
while(true) {
//all iteration are done. return sum
if (idx >= dimension.size())
return retSum;
if (idxV[idx] == 0) {
idxV[idx] = dimension[idx];
idx++;
} else {
idxV[idx];
break;
}
}
retSum += getElement(idxV);
}

leochen40505
May 27, 2019 Open Chat in New Window
 leochen40505 May 27, 2019