AMR-KELEG's blog

[Geometry] 2017 United Kingdom and Ireland Programming Contest (UKIEPC 2017) — Problem B — Breaking Biscuits
By AMR-KELEG, history, 7 years ago, In English

Could you please tell me how to solve problem B (Breaking Biscuits) in the gym contest http://codeforces.net/gym/101606 ?

Thanks

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

»
7 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

I think you just need to find convex hull (Graham scan for example). Than you have to find for each point of convex hull the point which is furthest from it (Rotating calipers technique — O(n) or ternary search — O(nlogn)). The answer is minimum of these distances.

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

    Could you please elaborate more?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 16   Vote: I like it 0 Vote: I do not like it

      First you create convex hull (just use one algorithm) and sort them in clockwise order. Then for the first point you check all other points and take the one with maximum distance (also you must save the index of this point). And then since polygon is convex when searching for next maximum (for point that is next in clockwise order), you can go around the polygon clockwise ans while next point (starting from index saved before) is further, increase index. Complexity of creating convex hull is O(nlogn) and you can find these distances in O(n) because you will go at most one circle around convex hull polygon.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        If for each point, we find the point farthest from it, and take the minimum over all these maximum distances, there may still be a better solution. You only need to consider the first sample to see this. The sample is a rectangle of height = 5 and width = 2. The farthest point from each vertex is always on the diagonal. However, we can just place the rectangle inside a cup with diameter of 2. (place the rectangle with the long side parallel to the cup).

        The correct solution is VladaMG98's.

        It is always optimal to place the polygon with one edge parallel to the cup. Note that if we have a solution where this is not the case, we can rotate the polygon so that a side is touching the side of the cup which will give us a better answer (draw some pictures to convince yourselves. We can try placing any edge on the side of the cup, and for each find the vertex farthest away from it.

        Input sizes are so small we can do N^2 solution very easily. You still need Convex Hull for this. Since N is at most 100, we can do an N^3 solution without using convex hull at all just to make coding easier. It's a similar idea. Try figuring it out if you want.

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

          You are right. For every edge we must find the point which is furthest from our edge (the line on which our edge lies) and than take minimum of these distances. Although everything else is the same.

          → Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

For every edge, you need to find the furthest vertex to that edge, and then just take the minimum of all of those distances.

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

    Could you please elaborate more?

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

    There is not only convex polygon allows in task. Does it correct for polygon with heart shape where height is more less then wide? It seems we can construct such shape that answer is only heart height (no rotation), but any rotation will increase height.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I have probably made a mistake, never mind.

    → Reply