DanAlex's blog

By DanAlex, 10 years ago, In English

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 !



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.


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.



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.


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()
    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.

  • Vote: I like it
  • +42
  • Vote: I do not like it

9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, Nice problems, but I have a question concerning the case when there is a polygon that must be moved through a group of polygonal obstacles. Actually the Minkowsky's sum for polygons is used. Let's suppose the moving polygon is a square , having its coordinates (0,0), (1,0), (1,1), (0,1) , the obstacles are also squares, (3,0), (4,0), (4,1), (3,1) and, respectively, (3,2), (4,2), (4,3), (3,3). It is obvious that the moving polygon can pass between the obstacles but after "shrinking" the corresponding point wouldn't pass through the "augmented" obstacles. Maybe for squares or rectangles this can be easily modified but what's happening in the general case? What polygons should be "summed up"?

  • »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hello, I was left wondering the same thing, but the author's solution is right, and I understood it looking at his code. In your example, the expanded polygons of the obstacles are squares (2,-1) to (4,1) and (2,1) to (4,3). These two 2x2 squares touch each other, but no point is inside the other square and no segments intersect each other (integer math so not prone to precision errors), so the edge between the squares — (2,1) to (4,1) is valid for our shortest path calculation later. The polygons that should be summed up are — for each obstacle polygon point, check each of our robot points, and if they coincide, where would our robot anchor point be? Hence, a 1x1 robot and a 1x1 square would produce a 2x2 square, lots of same points, but they get removed in the convex hull calculation. Really nice problem!

6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I haven't read about intersection graphs before, so most of the article went above my head. Could you give me a link to some resources related to that? I'd be really grateful