google kickstart round f. #3 Star Trappers (updated 09/24)

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435bae/0000000000888d45

NOTE

09/24

• how to select possible candidates for three white stars?
• how to determine the three white stars region contains the blue star?
  • if blue star is over the two lines and under the one line?

Problem

John and Ada are sitting on the grass above a small hill. It is midnight and the sky is full of stars. The sky looks like a 2D plane from so far away and the stars look like points on that plane. Ada loves blue stars and suddenly she notices one, while all the other stars in the sky are white. She loves the blue star so much that she wants to trap it. And she asks John for help.

Ada will tell John the position of the blue star and he has to trap it. To trap it, John has to draw a polygon in the sky with his buster sword, so that the blue star is strictly inside the polygon (not on the border of the polygon) and the polygon has the smallest possible perimeter. The vertices of the polygon must be the white stars.

Even though John is super awesome, he needs your help. Given the positions of the white stars and the blue star, you need to find out whether John can trap the blue star and if he can, also find the minimum length of the perimeter of the polygon he will use.

Input

The first line of the input gives the number of test cases, T. T test cases follow.
For each test case, the first line contains an integer N, it denotes the number of white stars in the sky.
The next N lines will each contain two integers, Xi and Yi. The i-th pair of integers denotes the x and y coordinates of the i-th star in the sky.
After these N lines, there will be one last line, which will contain two integers, Xs and Ys, which denote the x and y coordinates of the blue star.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum length of the perimeter of the polygon drawn to trap the shooting star. If it is impossible for John to draw a polygon that traps the star, then y should be IMPOSSIBLE.

y will be considered correct if it is within an absolute or relative error of 10−6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

Limits
Memory limit: 1 GB.
1≤T≤100.
0≤Xi,Yi≤106, for all i.
0≤Xs,Ys≤106.
No two stars (including the blue star) will have the same position.

Test Set 1
Time limit: 5 seconds.
1≤N≤10.
Test Set 2
Time limit: 5 seconds.
1≤N≤45.
Test Set 3
Time limit: 50 seconds.
For at most 10 test cases:
1≤N≤300.

For the remaining test cases:
1≤N≤60.

Solution (Work in progress)

TBD: FAIL. just passed the samples.

from math import sqrt, isclose

def solve(white_stars, blue_star):
    def get_distances(coordinates, point_x):
        return [get_distance(point_x, point_y) for point_y in coordinates]
        
    def get_distance(point_x, point_y):
        x,y = point_x
        xi,yi = point_y
        return sqrt(abs(x-xi)**2 + abs(y-yi)**2)
    
    def get_perimeter(coordinates):
        perimeter = 0

        for point_a, point_b in zip(coordinates, coordinates[1:] + [coordinates[0]]):
            distance = get_distance(point_a, point_b)
            perimeter += distance
            print (f'get_perimeter({point_a}, {point_b})', perimeter, distance)
        return perimeter
        
    if len(white_stars) < 3:
        return 'IMPOSSIBLE'
    
    # FIXME: how to select three white stars??
    # step 1. calculate three lines of the y = ax + b form
    # step 2. for each line, check blur star is over or under the line.
    # step 3. blue star should be over two lines, and under the one line. 
    def is_over_the_line(two_points, point):
        (x1, y1), (x2, y2) = two_points
        x, y = point

        if x1 - x2 == 0: 
            # case of vertical line at x1.
            # True if `x` is right to `x1`. Otherwise False.
            print (f'is_over_the_line({two_points}, {point}): x={x1}, ret: {x > x1}')
            return x > x1
        
        if y1 - y2 == 0:
            # case of horizontal line at y1.
            print (f'is_over_the_line({two_points}, {point}): y={y1}, ret: {y > y1}')
            return y > y1

        a = (y1 - y2) / (x1 - x2)
        b = y1 - a*x1   #a*x1 + b = y1

        if y > a*x + b:
            ret = True
        else:
            ret = False
        print (f'is_over_the_line({two_points}, {point}): a:{a}, b:{b}, ret:{ret}')
        return ret
        
    def take_candidate(white_stars):
        distances = get_distances(white_stars, blue_star)
        coordinates_with_distance = zip(white_stars, distances)
        nearest_white_stars = sorted (coordinates_with_distance, key=lambda a: a[1])[:3]
        nearest_white_stars = [coord for coord, _ in nearest_white_stars]
        print ('take_candidate', nearest_white_stars)
        return nearest_white_stars

    def contains_point(three_stars, blue_star):
        count_over_the_line = 0
        three_stars_shifted = three_stars[1:] + three_stars[:1]
        for point_a, point_b in zip(three_stars, three_stars_shifted):
            count_over_the_line += is_over_the_line([point_a, point_b], blue_star)
        
        if count_over_the_line == 2:
            return True
        return False

    three_stars = take_candidate(white_stars)
    if contains_point(three_stars, blue_star):
        perimeter = get_perimeter(three_stars)
    else:
        return 'IMPOSSIBLE'
        
    return perimeter