TopCoder problem "QuadrilateralSearch" used in SRM 227 (Division I Level Three)

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

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.

Returns: 179.10027343916573

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

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.

Returns: 4965.195939678256

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3514

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6516&pm=3514

Writer:

timmac

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Advanced Math, Geometry, Search, Simple Search, Iteration