QuadrilateralSearch | Topcoder Archive

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

```
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.
```
20
```
```
31
```
```
6
```
```
5
```
```
Returns: 179.10027343916573
```
Here, we have six points, so there are 15 possible quadrilaterals. We choose the largest of these.
```
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.
```
100
```
```
1200
```
```
20
```
```
139
```
```
Returns: 4965.195939678256
```

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.