Connection Status:
Competition Arena > QuadrilateralSearch

QuadrilateralSearch

SRM 227 · 2005-01-22 · by erinn

SRM 227 · 2005-01-22 · by erinn · Advanced Math, Geometry, Search, Simple Search, Iteration
Class Name: QuadrilateralSearch
Return Type: double
Method Name: findLargest
Arg Types: (int, int, int, int)
Problem Statement

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.

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
0)
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.

1)
20
31
6
5
Returns: 179.10027343916573

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

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

3)
100
1200
20
139
Returns: 4965.195939678256
4)
123
654321
123
542
Returns: 70.12880984159676
28)
1000
843448655
11
826017634
Returns: 36593.97467726603

1000 11

Submissions are judged against all 53 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class QuadrilateralSearch with a public method double findLargest(int d, int n, int c, int g) · 53 test cases · 2 s / 256 MB per case

Submitting as anonymous