• Create Account

### #Actualclb

Posted 09 February 2012 - 05:16 PM

Here's my Theta(n^2) try for the original problem:


struct Point
{
int x,y;
};

int MinAbsDistance(const Point &a, const Point &b)
{
return min(abs(a.x - b.x), abs(a.y - b.y));
}

/// Returns the size of the largest square centered at the point at index 'centerIndex'.
int SquareSizeCenteredAt(Point *points, int numPoints, int centerIndex)
{
int squareSize = INT_MAX;
for(int i = 0; i < numPoints; ++i)
if (i != centerIndex)
squareSize = min(squareSize, MinAbsDistance(points[i], points[centerIndex]));
return squareSize;
}

/// Finds the position and size of the largest square centered at some point of the input array.
void FindLargestSquareCenteredAt(Point *points, int numPoints, int *outCenterIndex, int *outSquareSize)
{
*outSquareSize = 0;
// Try each point in turn for the center point.
for(int i = 0; i < numPoints; ++i)
{
// What's the largest square that can be centered around this point?
int size = SquareSizeCenteredAt(points, numPoints, i);
// Beat the previous found record?
if (size > *outSquareSize)
{
*outSquareSize = size;
*outCenterIndex = i;
}
}
}


I ran it through the compiler to see it builds, but have not actually run it even once. It is not applicable as-is for your modified problem, where the center of the square does not have to lie at a center of an existing point.

### #1clb

Posted 09 February 2012 - 05:16 PM

Here's my O(n^2) try for the original problem:


struct Point
{
int x,y;
};

int MinAbsDistance(const Point &a, const Point &b)
{
return min(abs(a.x - b.x), abs(a.y - b.y));
}

/// Returns the size of the largest square centered at the point at index 'centerIndex'.
int SquareSizeCenteredAt(Point *points, int numPoints, int centerIndex)
{
int squareSize = INT_MAX;
for(int i = 0; i < numPoints; ++i)
if (i != centerIndex)
squareSize = min(squareSize, MinAbsDistance(points[i], points[centerIndex]));
return squareSize;
}

/// Finds the position and size of the largest square centered at some point of the input array.
void FindLargestSquareCenteredAt(Point *points, int numPoints, int *outCenterIndex, int *outSquareSize)
{
*outSquareSize = 0;
// Try each point in turn for the center point.
for(int i = 0; i < numPoints; ++i)
{
// What's the largest square that can be centered around this point?
int size = SquareSizeCenteredAt(points, numPoints, i);
// Beat the previous found record?
if (size > *outSquareSize)
{
*outSquareSize = size;
*outCenterIndex = i;
}
}
}


I ran it through the compiler to see it builds, but have not actually run it even once. It is not applicable as-is for your modified problem, where the center of the square does not have to lie at a center of an existing point.

PARTNERS