Statistics

Problem Statement

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.

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

1. 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

2. 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

3. 7995

   25000

   Returns: 0.002543062783060902

4. 1

   3

   Returns: 0.6885306552897291

5. 0

   1000

   Returns: 0.012695160182229447

6. 10000

   5000

   Returns: 0.0035310390901411746

7. 7000

   4999

   Returns: 0.003949749379897588

8. 0

   4889

   Returns: 0.0036962718898736653

9. 10000

   2500

   Returns: 0.006200603687543239

10. 3456

    1250

    Returns: 0.012627514885098957

11. 5000

    8000

    Returns: 0.003253670188028391

12. 10276

    23265

    Returns: 0.0026075742156626428

13. 15390

    3160

    Returns: 0.0050773611279361

14. 1914

    18565

    Returns: 0.0025909794103504084

15. 14732

    23682

    Returns: 0.0025860367295155633

16. 9289

    20459

    Returns: 0.002578640912020997

17. 11730

    12126

    Returns: 0.0027905961037583563

18. 10078

    18451

    Returns: 0.0026075742156626428

19. 7528

    10201

    Returns: 0.0028970645275776937

20. 3569

    24157

    Returns: 0.0025662659106435487

21. 5770

    14794

    Returns: 0.0026825160813567536

22. 8294

    25000

    Returns: 0.0026075742156626428

23. 12675

    25000

    Returns: 0.0025465494212229657

24. 2456

    25000

    Returns: 0.0025582730996991624

25. 1848

    25000

    Returns: 0.0025320834094712456

26. 3316

    25000

    Returns: 0.0025582730996991624

27. 4906

    25000

    Returns: 0.0025320834094712456

28. 2672

    25000

    Returns: 0.0025582730996991624

29. 19097

    25000

    Returns: 0.002557061792719473

30. 0

    25000

    Returns: 0.002542557902248764

31. 20000

    25000

    Returns: 0.002558396164934467

32. 13857

    2

    Returns: 0.7384546376067971

33. 13605

    2

    Returns: 0.7512068644436205

34. 8753

    2

    Returns: 0.6709526267474818

35. 19907

    2

    Returns: 0.5502585484813174

36. 306

    2

    Returns: 0.580150369772959

37. 3876

    3

    Returns: 0.8634346761321042

38. 327

    3

    Returns: 0.7699892129802773

39. 15819

    3

    Returns: 0.5017787764614248

40. 11168

    4

    Returns: 0.6209058718117819

41. 3762

    4

    Returns: 0.6278570920791131

42. 0

    3000

    Returns: 0.0053171745173182395

43. 2657

    2

    Returns: 0.4487007515408176

44. 12321

    2

    Returns: 0.615729203993725

45. 15952

    2

    Returns: 0.8629558001353441

46. 2215

    3

    Returns: 0.8157487800137614