Блог пользователя AMR-KELEG

[Geometry] 2017 United Kingdom and Ireland Programming Contest (UKIEPC 2017) — Problem B — Breaking Biscuits
Автор AMR-KELEG, история, 6 лет назад, По-английски

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

Thanks

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Could you please elaborate more?

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 16   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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.

        → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

→ Ответить