| | There is an unknown polygon drawn on a 2-dimensional plane. It is not necessarily convex, it is rather not convex in majority of test cases. Your task is to estimate its shape as precisely as possible.
Problem specification
Initially you have only the following information about the polygon:
- Both X and Y coordinates of each vertex are between 0 and 9,999, inclusive.
- No two vertices coincide.
- No three vertices are located on the same straight line.
In order to gather information about the polygon, you will be casting rays and receiving data about each ray's first intersection point with the polygon. You can cast up to 1,000 rays. You cast a ray by calling the library function sendRequest in the library RayCaster. In each request, you send 4 integers (x1, y1, x2, y2). The server casts a ray from point (x1, y1) through the point (x2, y2) and beyond. The return value is an array of 2 doubles giving the approximate coordinates of the closest intersection point found (closest to x1, y1). If no intersection is found, an array of length 0 is returned.
Each of the parameters x1, y1, x2 and y2 must be between 0 and 9,999, inclusive, and the points (x1, y1) and (x2, y2) must not be the same. Once the closest intersection point is found, the server will add a small amount of noise to it. More exactly, the reported intersection point will be shifted along the ray by a distance equal to shift = D * x, where x is a random value generated from a normal distribution with a mean of 0 and a standard deviation of 1. Note that the intersection calculation is exact, without any randomness, and random shift is added only after the exact intersection point (if any) is found. The shift may be positive or negative.
You don't have to send all 1,000 requests. It is possible to send a smaller amount. Once you have chosen to stop sending requests, you should return your best guess of the polygon's shape. The guess should be a polygon itself. It should contain between 3 and 1,000 vertices, inclusive. Both X and Y coordinates of each vertex must be between 0 and 9999, inclusive. It should represent a simple polygon: two consecutive sides intersect only in their common vertex, two non-consecutive sides do not intersect.
Scoring
Scoring will be done as follows. Let A be the area of the original unknown polygon, B the area of your estimate, C the area of their intersection and R the number of requests you've sent. Your raw score for a single test case will be reported as 1.0 - 0.99R / P * C / max{A, B}. Note that lower score indicates a better guess. If something goes wrong during your solution's execution (time/memory limit, runtime error, etc.) or if your guess does not satisfy to the restrictions from the previous paragraph, your score will be 2.0. In order to calculate overall scores, raw scores will first be normalized. If your raw score for a test case is 2.0, your normalized score will be equal to 0.0. Otherwise, if you have a score of yourScore for a test case and the best (minimum) score for this test case is bestScore, your normalized score will be equal to (bestScore + 0.01) / (yourScore + 0.01). Your overall score will be equal to 1,000,000.0 * (the arithmetic average of your normalized scores for all test cases).
Implementation
You need to implement a single method estimate. Its input parameters are D (determines the amount of noise added) and P (used for scoring calculation). The return value needs to encode your estimated polygon as an int[] of 2*M elements where elements 0 and 1 are X and Y coordinates of vertex 0, elements 2 and 3 are the X, Y coordinates of vertex 1, ..., elements 2*M-2 and 2*M-1 are the X, Y coordinates of vertex M-1. Here M is the number of vertices in your estimate of the polygon.
In order to make requests, you can call a static library method sendRequest in class RayCaster (as described above). If you send an incorrect request, the return value will be a double[] containing a single element equal to 0.
Test case generation
Each test case is generated as follows:
# random(L, R) generates a real value uniformly, at random, between L and R
a := random(0.0, 1.0)
D := 5.0 + 45.0 * a * a
P := random(10.0, 100.0)
# randomInt(L, R) generates an integer value uniformly, at random, between L and R, inclusive
# number of polygon's vertices
N := randomInt(10, 100)
# coordinates, in no particular order
for i = 0, 1, ..., N-1:
X[i] = randomInt(0, 9999)
Y[i] = randomInt(0, 9999)
# regenerate if something is bad
while (X[i], Y[i]) coincides with (X[j], Y[j]), j < i, or
(X[i], Y[i]), (X[j], Y[j]) and (X[k], Y[k]), k < j < i,
lie on the same straight line:
X[i] = randomInt(0, 9999)
Y[i] = randomInt(0, 9999)
# generate a proper order
Assume that points go in order 0, 1, 2, ..., N-1.
for i = 0, 1, ..., N-3:
for j = i+2, i+3, ..., N-1:
if (i == 0) and (j == N-1):
break
A := segment between (X[i], Y[i]) and (X[i+1], Y[i+1])
B := segment between (X[j], Y[j]) and (X[(j+1)%N], Y[(j+1)%N])
if A and B intersect:
# Remove (i)-(i+1) and (j)-(j+1) sides.
# Add (i)-(j) and (i+1)-(j+1) sides.
# This reverses the order of the points from i+1 to j.
Reorder points as 0, 1, ..., i, j, j-1, ..., i+1, j+1, j+2, ..., N-1.
Restart the "for i" cycle above from scratch.
# once done, 0, 1, .., N-1 order defines a valid polygon
Tools
A visualizer/offline tester is available. You can check its source code for an exact implementation of test case generation, request handling and scoring. It also allows manual playing. |