2009 World Finals hosted by Kth CPC 2009 ou acm progratmimilg牌IM|m Problem F Deer-Proof fence Input: fence. in Uncle Magnus has planted some young saplings on his farm as part of his reforestation project. Unfortunately, deer like to eat tender sapling shoots and leaves, making it necessary to build protective fences around them Since deer and other sapling nibblers can reach partway over the fence, every fence must lie at least a minimum distance(a margin) from each saplin Deer-proof fencing is quite expensive, so Uncle Magnus wants to minimize the total length of fencing used Your job is to write a program that computes the minimum length of fencing that is required to enclose and protect the saplings. Fences may include both straight and curved segments. You may design a single fence that encloses all saplings or multiple fences that enclose separate groups of saplings Figure 6 shows two example configurations, each consisting of three saplings with different margin requirements. In the top configuration, which corresponds to the first sample input, the minimum-length solution consists of two separate fences. In the bottom configuration, which corresponds to the second sample input, the minimum-length solution consists of a single fence (.0(2.0) (10,0) Three Saplings ●= Sapling Location =Deer-proof Fence Deer-proof Fence (0,0)(2,0 (10,0) 0111213 Three Sapling Figure 6: Deer-proof fences.Problem F Deer-Proof Fence Input: fence.in Uncle Magnus has planted some young saplings on his farm as part of his reforestation project. Unfortunately, deer like to eat tender sapling shoots and leaves, making it necessary to build protective fences around them. Since deer and other sapling nibblers can reach partway over the fence, every fence must lie at least a minimum distance (a margin) from each sapling. Deer-proof fencing is quite expensive, so Uncle Magnus wants to minimize the total length of fencing used. Your job is to write a program that computes the minimum length of fencing that is required to enclose and protect the saplings. Fences may include both straight and curved segments. You may design a single fence that encloses all saplings or multiple fences that enclose separate groups of saplings. Figure 6 shows two example configurations, each consisting of three saplings with different margin requirements. In the top configuration, which corresponds to the first sample input, the minimum-length solution consists of two separate fences. In the bottom configuration, which corresponds to the second sample input, the minimum-length solution consists of a single fence. Figure 6: Deer­proof fences