TCO12 Championship Round — PolygonEstimation

Problem statement

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.99^{R / 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.

Legacy definition

Class: PolygonEstimation

String displayTestCase(String s)
int[] estimate(double D, double P)
RayCaster.double[] sendRequest(int x1, int y1, int x2, int y2)

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

Example 0

Input

"1"

Legacy example display output

"N = 91
D = 20.61354534858991
P = 45.93229603372773"

Example 1

Input

"2"

Legacy example display output

"N = 21
D = 13.726055904597247
P = 12.305219227908449"

Example 2

Input

"3"

Legacy example display output

"N = 70
D = 35.0351033657376
P = 20.77148561706445"

Example 3

Input

"4"

Legacy example display output

"N = 74
D = 39.184059544374826
P = 25.64704548673069"

Example 4

Input

"5"

Legacy example display output

"N = 99
D = 13.449951930454125
P = 14.373876861986961"

Example 5

Input

"6"

Legacy example display output

"N = 83
D = 48.53947829437732
P = 65.72635643776047"

Example 6

Input

"7"

Legacy example display output

"N = 18
D = 10.937181982134508
P = 37.5250749757682"

Example 7

Input

"8"

Legacy example display output

"N = 62
D = 12.578329816723187
P = 55.54124266699317"

Example 8

Input

"9"

Legacy example display output

"N = 12
D = 25.591029594435025
P = 84.87989527259487"

Example 9

Input

"10"

Legacy example display output

"N = 72
D = 8.348685347691859
P = 11.926436040241912"