Hello ! This week I will present you some geometry problems. As the last week you'll have the statements first and the solutions below. I would also like to hear your feedback about my blog. Enjoy reading !

Statements

Hallway

This problem is from a Romanian judge. I will present the statement in English. Basically you have a hallway of size M*N. There are K columns at integer coordinates. Your task is to say the maximum size of a ball that can travese the hallway in such way that is doesn't get stuck. Restrictions: 1 ≤ M, N, K ≤ 1000 , print the result with 8 decimals rounded down.

Robot

From the same Romanian judge. You have a robot consisting of a N-polygon ( N<=10 ). Your robot position is defined as the point with the minimum y and ( in case of equality ) the minimum x. You have M ( M<=25 ) polygon obstacles with less than 251 points. Your task is to get to the final point ( fx,fy ) on the minimum length road in such way that the robot does not hit (intersect) any obstacle. You have to print the minimum length of this road. For all the polygons the points are given trigonometrically.

Solutions

Hallway

To obtain a first solution to this problem you have to think the problem "upside down". Let's assume we have already computed the radius of the ball. So you have to verify if you can traverse the hallway.

Instead of traversing the hallway with the ball , we'll shrink the ball to a point ( the red one in the picture ) and transform the obstacles into balls.

Now you can check is the point can traverse the hallway just by making the intersection graph of the balls and upper and downer sides of the hallway. We can binary search the size of the ball and we'll optain a O(K^2 log M) algorithm.

A faster solution would continue on the idea of the graph. You can associate costs in that graph : the distance between two obstacles or sides / 2. Now your problem will be reduced to calculating the minimum spanning tree in this graph until we have joined the upper and the downer sides togeather. How comes that ? When you're making the minimum spanning tree you are adding edges with ascending costs. So , if we have joined the upper and the downer side we know that the bigest edge in the road between them is our size.

Now let's analyse the complexity. We can use the Kruskal algorithm in O(K^2 log K). This is not a great improvement. On the other hand , we can use Prime in O(K^2). That's a nice solution , isn't it ?

Here is my source.

Robot

The small number of polygons suggests that the difficulty of the problem is to find a way to solve the problem as simple as possible.

If you read the post until here , you probablly expect the robot to be shrinked. You're right ! Let's take an obstacle with K points. We'll virtually move the anchor point in every point of the K and we'll obtain a new set of points. From this set we'll make a polygon just by making a convex hull in O(N*K log (N*K)). Here is some code:

void expand()
{
    sort(robot.begin(),robot.end());
    for (size_t i=0;i<obstacle.size();++i)
    {
        int size = obstacle[i].size();
        for (int j=0;j<size;++j)
            for (size_t k=0;k<robot.size();++k)
                obstacle[i].push_back( trans(obstacle[i][j],robot[0],robot[k]) );
        convex_hull( obstacle[i] );
    }
}

One right abordation in such cases ( when we deal with distances on a plane ) is to use a graph. We will consider all the points to be vertexes and we'll consider all valid edges. An edge is valid if it doesn't intersect with the interior of a polygon. We can solve that in O(K) for every polygon and pair of points.

Now our problem is how can we check if a segment intersects the interior of a polygon. This is quite a basic problem. You have to consider the following cases: at least one point is in the interior of the polygon , both points are on the edges of the polygon and the segment cuts a segment from the polygon. Checking if one point is in interior of a polygon goes like that:

int area(vector<pi> v)
{
    int out = 0;
    for (size_t i=0;i<v.size()-1;++i)
        out += cross(v[i],v[i+1]);
    out = max(out,-out);
    return out;
}
 
int tarea(pi A,pi B,pi C)
{
    int out = cross(A,B) + cross(B,C) + cross(C,A);
    out = max(out,-out);
    return out;
}
 
int parea(vector<pi> v,pi a)
{
    int out = 0;
    for (size_t i=0;i<v.size()-1;++i)
        out += tarea(v[i],v[i+1],a);
    return out;
}

bool inside(pd V,pd A)
{
    int area_v = area(V);
    int area_a = parea(V,A);
  
    if ( area_v == area_a ) return 1;
    return 0;
}

Once the graph is made , we can start a minimum road algorithm ( such as Dijkstra or Bellman-Ford ).

Here is a source.

Bonus: the shrinking trick can be used in this problem. Here is my solution.