Cake cuts

You are presented with a rectangular cake whose sides are of length X and Y.
The cake has been cut into (N + 1) pieces by making N
 straight cuts along the first side and N straight cuts along the second side.

The cuts are represented by two non-empty zero-indexed arrays A and B
 consisting of N integers. More precisely, A[i] such that 0 ≤ i < N
 represents the position of a cut along the first side, and B[j] such that
 0 ≤ j < N represents the position of a cut along the second side.
We could also make a different number of cuts on the second side but for now the number of cuts is equal on both sides.

The goal is to find the K-th piece of cake in order of size, starting with
 the largest piece first. We will consider the size of a piece to be its area.

N is an integer within the range [1..40,000];
X and Y are integers within the range [2..400,000,000];
K is an integer within the range [1..(N+1)*(N+1)];
each element of array A is an integer within the range [1..X−1];
each element of array B is an integer within the range [1..Y−1];
A[i − 1] < A[i] and B[i − 1] < B[i], for every i such that 0 < i< N;
1 ≤ A[i] − A[i − 1], B[i] − B[i − 1] ≤ 10,000, for every i such that 0 < i < N;
1 ≤ A[0], B[0], X − A[N − 1], Y − B[N − 1] ≤ 10,000

	int solution(int X, int Y, int K, int A[], int B[], int N) {
	if (A != NULL && B != NULL &&
	N > 0 && N <= 40000 &&
	X > 1 && Y > 1 && K > 0 &&
	X <= 400000000 && Y <= 400000000 &&
	K <= (N + 1)*(N + 1))
	{
	int i, j, nr, nj, sx, sy, max = 0, y = 0, *S = new int[K];
	while (true)
	{
	max = 0;
	for (i = 0; i <= N; i++)
	for (j = 0; j <= N; j++)
	{
	sx = (i == 0) ? A[0] : (((i == N) ? X : A[i]) - A[i - 1]);
	sy = (j == 0) ? B[0] : (((j == N) ? Y : B[j]) - B[j - 1]);
	if (sx > 0 && sy > 0)
	nr = sx*sy;// area of cake piece
	else
	return -1;
	if (nr > max)
	{
	for (nj = 0; nj < y&&S[nj] != nr; nj++);// not maxed before
	if (nj == y) S[y] = max = nr;
	}
	}
	++y;// next big cake piece
	if (y == K)return max; // oh, you are here
	}
	}
	return -3;
	}

view raw CakeCuts.cpp hosted with ❤ by GitHub

   - first the biggest piece is searched, then the second biggest piece .. all is done K times, and when the K iteration is reached, the size of the biggest piece of cake that was found, is returned