Problem Statement |
| | You are given a set of points on a two-dimensional plane.
You have to construct some polygons which have these points as vertices. More exactly:
- Each vertex of each polygon must be a point from the given set.
- Each point from the given set can belong to at most one of the constructed polygons.
Each polygon that you construct must be a quality polygon. It is a convex poygon which has sides of approximately equal length, and the vertices are at approximately equal distance from the center of the polygon. More formally, a quality polygon must satisfy to the following restrictions:
- It is a convex polygon.
- No 3 consecutive vertices of a polygon lie on the same straight line. In other words, the polygon must be strictly convex.
- If Lmax and Lmin are maximal and minimal length of polygon side, then the following condition must hold: Lmin/Lmax ≥ 1 - (sidesDiff/100).
- If Dmax and Dmin are maximal and minimal out of distances from the center of the polygon to its vertices, then the following condition must hold: Dmin/Dmax ≥ 1 - (radiiDiff/100). The center of the polygon is defined as a point where both X and Y coordinates are equal to the arithmetic average of X and Y coordinates of polygon's vertices, correspondingly.
Let's define a size of a polygon as the square of the number of its vertices. Your task is to maximize the sum of sizes of polygons that you constructed.
Implementation Details
Your code should implement one method choosePolygons(int[] points, int sidesDiff, int radiiDiff). points gives you the set of points: point i (0-based) has coordinates (points[2*i], points[2*i+1]). sidesDiff and radiiDiff are parameters from the definition of quality polygon.
You must return a set of polygons you've constructed from these points as a String[]. Each element of your return must describe one polygon and should be formatted as a space-separated list of its vertices in clockwise or counterclockwise order. Each vertex is given as its 0-based index, in the same order as the vertices are given in points.
Test Case Generation
In the text below "chosen" always means "chosen uniformly, at random", unless another distribution is specified.
The number of points in the set is chosen either between 50 and 499, inclusive, or between 500 and 5000, inclusive (either interval is chosen with probability 0.5). The points are sampled from one of random distributions generated as follows. The number of distributions is chosen between 5 and 20, inclusive. Each distribution has a center at (xD, yD), radius rD and standard deviation dD. For each distribution its center is chosen as the center of previous one (with probability 1/3) or as a new point, with both xD and yD being integers between 50 and 649, inclusive. rD and dD are chosen as floating-point numbers between 30 and 270 and 10 and 100, respectively.
For each new point, the distribution to sample it from is chosen. Once it is chosen, r is generated as abs(rnd * dD + rD), where rnd is a sample from standard normal distribution, and angle is chosen as a floating-point value in 0..2*PI. After this, the coordinates of the point are set to (xD + r * cos(alpha), yD + r * sin(alpha)), rounded to integer values. Finally, it is checked that both coordinates of the new point are between 0 and 699, inclusive, and that it is distinct from all previously generated ones; otherwise, the point is re-generated from the start.
Both sidesDiff and radiiDiff are chosen uniformly between 1 and 20, inclusive.
Scoring
Your score for an individual test case will be the sum of sizes of your returned polygons. If your return has invalid format or specifies any invalid polygons, your score for the test case will be 0. Your overall score will be calculated in the following way: for each test case where your score is not 0, you get 1 point for each competitor you beat on this test case (i.e., your score on a test case is larger than this competitor's score) and 0.5 points for each competitor you tie with (a tie with yourself is not counted); finally, the sum of points is divided by (the number of competitors - 1).
Tools
A visualization tool is provided for offline testing. It also allows manual play. |
| |
Definition |
| | | Class: | QualityPolygons | | Method: | choosePolygons | | Parameters: | int[], int, int | | Returns: | String[] | | Method signature: | String[] choosePolygons(int[] points, int sidesDiff, int radiiDiff) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The memory limit is 1024 MB and the time limit is 10 seconds (which includes only time spent in your code). |
| - | There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB. |
| - | The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here. |
| - | There are 10 example test cases and 100 full submission test cases. |
| |
Examples |
| 0) | |
| | | Returns: "seed = 1
NP = 50
sidesDiff = 20
radiiDiff = 20
" | A possible solution for this test case is shown below. Note that it is not necessarily the optimal solution.
 |
|
|
| 1) | |
| | | Returns: "seed = 2
NP = 440
sidesDiff = 4
radiiDiff = 6
" | |
|
| 2) | |
| | | Returns: "seed = 3
NP = 2395
sidesDiff = 5
radiiDiff = 10
" | |
|
| 3) | |
| | | Returns: "seed = 4
NP = 3646
sidesDiff = 14
radiiDiff = 5
" | |
|
| 4) | |
| | | Returns: "seed = 5
NP = 377
sidesDiff = 8
radiiDiff = 3
" | |
|
| 5) | |
| | | Returns: "seed = 6
NP = 2773
sidesDiff = 3
radiiDiff = 14
" | |
|
| 6) | |
| | | Returns: "seed = 7
NP = 382
sidesDiff = 4
radiiDiff = 17
" | |
|
| 7) | |
| | | Returns: "seed = 8
NP = 254
sidesDiff = 16
radiiDiff = 3
" | |
|
| 8) | |
| | | Returns: "seed = 9
NP = 1117
sidesDiff = 11
radiiDiff = 11
" | |
|
| 9) | |
| | | Returns: "seed = 10
NP = 90
sidesDiff = 20
radiiDiff = 14
" | |
|
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)2020, TopCoder, Inc. All rights reserved.
