| We manufacture wafers for the production of computer chips. Our manufacturing
process is very cheap, but produces a large number of bad points on the surface
of the wafer. We need to be able to determine the largest rectangular area
that contains no bad points and thus can safely be used for a chip.
The wafer is square with a coordinate system where (0,0) refers to the bottom
left corner and (1,1) refers to the upper right corner. We can
automatically scan a wafer and find the coordinates of each bad point.
Your task is to develop an efficient algorithm that is given the coordinates of
the n bad points and that returns the area of the largest rectangle
with boundaries parallel to the coordinate system that contains no bad points.
To demonstrate that the algorithm is efficient, you will run it using values from a
random number stream defined recursively by
R0 = 111
Ri = 111*Ri-1 mod 323537 (for i>0)
This produces values that are uniformly distributed in the range 1 to 323537 and its
cycle length is 323536. Your program will be told how many R's to skip
(as a way of "seeding" the random
generator). The n points can be generated by the following code:
int R=1;
for(int j = 0; j < skip; j++) R = 111 * R % 323537;
for(int pt = 0; pt < n; pt++){
R = 111*R%323537; double x = R/323537.0;
R = 111*R%323537; double y = R/323537.0;
//x,y are the coordinates of this point ...
}
Given skip and n
return the largest area.
|