ChipArea | Topcoder Archive

Problem Statement

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

         R₀ = 111
         R_i = 111*R_i-1 mod 323537  (for i&gt;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 &lt; skip; j++) R = 111 * R % 323537;
for(int pt = 0; pt &lt; 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.

Definition

Class:: ChipArea
Method:: maxArea
Parameters:: int, int
Returns:: double
Method signature:: double maxArea(int skip, int n)
(be sure your method is public)

Notes

A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.

Constraints

skip will be between 0 and 20,000, inclusive.
n will be between 2 and 25,000, inclusive.

Examples

```
0
```
```
3
```
```
Returns: 0.6058657896932963
```
The first six random numbers give the 3 points as (0.00034308286223832206,0.038082197708453745),(0.22712394563836594,0.21075796585861895), (0.3941342103067037,0.7488973440441125). The biggest rectangular area that contains none of these is the area to the right of the third point which is approximately (1-.394)*(1-0) = .606
```
3
```
```
3
```
```
Returns: 0.6885306552897291
```
After skipping the first 3 random numbers, using the next six to produce 3 points gives approximately (0.211,0.394),(0.749,0.128),(0.164,0.224) The biggest area is the area to the right of first point and above the second point which is (1-.211)*(1-.128) = 0.69
```
7995
```
```
25000
```
```
Returns: 0.002543062783060902
```
```
0
```
```
3000
```
```
Returns: 0.0053171745173182395
```
```
2657
```
```
2
```
```
Returns: 0.4487007515408176
```
```
12321
```
```
2
```
```
Returns: 0.615729203993725
```
```
15952
```
```
2
```
```
Returns: 0.8629558001353441
```
```
2215
```
```
3
```
```
Returns: 0.8157487800137614
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.