Statistics

Problem Statement for "QuadrilateralSearch"

Problem Statement

You are given a circle of diameter d, with n points equally spaced around the circumference. The points are numbered in order around the circle 0, 1, 2, ... , n-1. Of those n points, c of them are colored red. The points that are colored red are given by the generator function (g * k) % n, for k = 0, 1, 2, ..., c-1.

You are given ints d, n, c, and g. You are to return a double indicating the largest area of a quadrilateral formed from four of the colored points.

Definition

Class:
QuadrilateralSearch
Method:
findLargest
Parameters:
int, int, int, int
Returns:
double
Method signature:
double findLargest(int d, int n, int c, int g)
(be sure your method is public)

Notes

  • The % operator is the modulus (remainder) operator.
  • Notice that it makes no difference which point is point 0, and in which direction around the circle the points are numbered.

Constraints

  • d will be between 1 and 1000, inclusive.
  • n will be between 4 and 1000000000, inclusive.
  • c will be between 4 and 500, inclusive.
  • c will be less than or equal to n.
  • g will be between 1 and n-1, inclusive, and will be relatively prime to n.

Examples

  1. 10

    13

    4

    3

    Returns: 48.9142858122447

    Here, we have only four points that are colored red: 0, 3, 6, and 9. It's just a simple matter of calculating the area of the quadrilateral.

  2. 20

    31

    6

    5

    Returns: 179.10027343916573

    Here, we have six points, so there are 15 possible quadrilaterals. We choose the largest of these.

  3. 1000

    80000

    50

    3

    Returns: 0.028489712517284715

    Here, with 50 points, there are a lot of possible quadrilaterals, but they are all long and flat, so even with such a large circle, they have a very small area.

  4. 100

    1200

    20

    139

    Returns: 4965.195939678256

  5. 123

    654321

    123

    542

    Returns: 70.12880984159676

  6. 1000

    1000000000

    500

    123456789

    Returns: 499718.04154028185

  7. 1000

    485941898

    4

    433465349

    Returns: 123623.29419658787

  8. 7

    917812527

    417

    469490540

    Returns: 24.49974943490183

  9. 492

    682914198

    146

    462852991

    Returns: 120989.03546487243

  10. 182

    860251130

    401

    543341301

    Returns: 16475.852613059076

  11. 468

    756769122

    135

    395816053

    Returns: 109470.37892456003

  12. 325

    485078038

    408

    363359455

    Returns: 52811.11983240667

  13. 952

    416576804

    461

    299709161

    Returns: 453118.75393075484

  14. 660

    884578408

    356

    771557771

    Returns: 217797.39977388317

  15. 18

    137434901

    270

    129105522

    Returns: 161.45094189116742

  16. 238

    541662396

    414

    250522913

    Returns: 28321.962405276536

  17. 820

    35066069

    77

    19578542

    Returns: 335969.27029588306

  18. 329

    581203641

    464

    21778868

    Returns: 54119.49559231788

  19. 850

    667594374

    140

    353088535

    Returns: 361212.89279805066

  20. 467

    869345368

    10

    715960973

    Returns: 103969.7748605738

  21. 821

    743402422

    138

    238955541

    Returns: 337020.45986480213

  22. 136

    652375401

    226

    436794958

    Returns: 9247.040229894676

  23. 861

    217663230

    132

    114844267

    Returns: 370618.2644862393

  24. 559

    22578896

    42

    13179731

    Returns: 156228.1137905926

  25. 47

    565474452

    259

    463590727

    Returns: 1104.2824814258315

  26. 787

    462866009

    125

    12733411

    Returns: 309613.5766123615

  27. 530

    902558745

    44

    517645126

    Returns: 139554.98199260558

  28. 1000

    19

    4

    12

    Returns: 417888.2011720174

  29. 1000

    843448655

    11

    826017634

    Returns: 36593.97467726603

    1000 11

  30. 1000

    445350462

    247

    81202091

    Returns: 499985.0057617111

  31. 1000

    12

    5

    5

    Returns: 466506.3509461097

  32. 1000

    1000

    500

    3

    Returns: 499995.0652140343

  33. 743

    1000000000

    500

    834874743

    Returns: 276023.10981023684

  34. 100

    1000000000

    500

    999999999

    Returns: 7.890246615793739E-13

  35. 1000

    1000000000

    4

    999999997

    Returns: 0.0

  36. 1000

    1000000000

    500

    1

    Returns: 7.890246789266087E-11

  37. 1000

    1000000000

    500

    900000001

    Returns: 475528.73675241636

  38. 100

    1200

    500

    139

    Returns: 4999.897192325458

  39. 997

    99987324

    497

    19999

    Returns: 4362.963038625141

  40. 100

    1000000000

    4

    999999997

    Returns: 0.0

  41. 1000

    1000000000

    500

    139

    Returns: 1.5328366735900545E-6

  42. 1000

    1000000000

    500

    999999999

    Returns: 7.890244013708525E-11

  43. 1000

    1000000000

    500

    797375799

    Returns: 499995.10110618296

  44. 1

    1000000000

    500

    453432457

    Returns: 0.4999996377227414

  45. 1000

    1000000000

    500

    2452347

    Returns: 499999.4246806687

  46. 1000

    1000000000

    500

    333333333

    Returns: 324759.7219832876

  47. 10

    1000000000

    40

    999999999

    Returns: 5.918152710379437E-15

  48. 1000

    1000000000

    500

    39993937

    Returns: 497592.35782514693

  49. 100

    120000013

    473

    109000121

    Returns: 4999.999779362206

  50. 1000

    1000000000

    500

    139139139

    Returns: 499973.4217768017

  51. 1

    1000000000

    500

    13

    Returns: 1.2859815141474766E-15

  52. 100

    533

    500

    4

    Returns: 4999.934860503239

  53. 512

    991999992

    477

    491999231

    Returns: 131071.98225481887

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.
This problem was used for: