********************************************************************** GOLD PROBLEMS ********************************************************************** Three problems numbered 1 through 3 ********************************************************************** Problem 1: Redundant Paths [Harry Wiggins, 2005] In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the rest of the herd are forced to cross near the Tree of Rotten Apples. The cows are now tired of often being forced to take a particular path and want to build some new paths so that they will always have a choice of at least two separate routes between any pair of fields. They currently have at least one route between each pair of fields and want to have at least two. Of course, they can only travel on Official Paths when they move from one field to another. Given a description of the current set of R (F-1 <= R <= 10,000) paths that each connect exactly two different fields, determine the minimum number of new paths (each of which connects exactly two fields) that must be built so that there are at least two separate routes between any pair of fields. Routes are considered separate if they use none of the same paths, even if they visit the same intermediate field along the way. There might already be more than one paths between the same pair of fields, and you may also build a new path that connects the same fields as some other path. PROBLEM NAME: rpaths INPUT FORMAT: * Line 1: Two space-separated integers: F and R * Lines 2..R+1: Each line contains two space-separated integers which are the fields at the endpoints of some path. SAMPLE INPUT (file rpaths.in): 7 7 1 2 2 3 3 4 2 5 4 5 5 6 5 7 INPUT DETAILS: One visualization of the paths is: 1 2 3 +---+---+ | | | | 6 +---+---+ 4 / 5 / / 7 + OUTPUT FORMAT: * Line 1: A single integer that is the number of new paths that must be built. SAMPLE OUTPUT (file rpaths.out): 2 OUTPUT DETAILS: Building new paths from 1 to 6 and from 4 to 7 satisfies the conditions. 1 2 3 +---+---+ : | | : | | 6 +---+---+ 4 / 5 : / : / : 7 + - - - - Check some of the routes: 1 - 2: 1 -> 2 and 1 -> 6 -> 5 -> 2 1 - 4: 1 -> 2 -> 3 -> 4 and 1 -> 6 -> 5 -> 4 3 - 7: 3 -> 4 -> 7 and 3 -> 2 -> 5 -> 7 Every pair of fields is, in fact, connected by two routes. It's possible that adding some other path will also solve the problem (like one from 6 to 7). Adding two paths, however, is the minimum. ********************************************************************** Problem 2: Roping the Field [Hal Burch, 2004] Farmer John is quite the nature artist: he often constructs large works of art on his farm. Today, FJ wants to construct a giant "field web". FJ's field is large convex polygon with fences along the boundary and fence posts at each of the N corners (1 <= N <= 150). To construct his field web, FJ wants to run as many ropes as possible in straight lines between pairs of non-adjacent fence posts such that no two ropes cross. There is one complication: FJ's field is not completely usable. Some evil aliens have created a total of G (0 <= G <= 100) grain circles in the field, all of radius R (1 <= R <= 100,000). FJ is afraid to upset the aliens, and therefore doesn't want the ropes to pass through, or even touch the very edge of a grain circle. Note that although the centers of all the circles are contained within the field, a wide radius may make it extend outside of the field, and both fences and fence posts may be within a grain circle. Given the locations of the fence posts and the centers of the circles, determine the maximum number of ropes that FJ can use to create his field web. FJ's fence posts and the circle centers all have integer coordinates X and Y each of which is in the range 0..1,000,000. PROBLEM NAME: roping INPUT FORMAT: * Line 1: Three space-separated integers: N, G, and R * Lines 2..N+1: Each line contains two space-separated integers that are the X,Y position of a fence post on the boundary of FJ's field. * Lines N+2..N+G+1: Each line contains two space-separated integers that are the X,Y position of a circle's center inside FJ's field. SAMPLE INPUT (file roping.in): 5 3 1 6 10 10 7 9 1 2 0 0 3 2 2 5 6 8 3 INPUT DETAILS: A pentagonal field, in which all possible ropes are blocked by three grain circles, except for the rope between fenceposts 2 and 4. OUTPUT FORMAT: * Line 1: A single integer that is the largest number of ropes FJ can use for his artistic creation. SAMPLE OUTPUT (file roping.out): 1 ********************************************************************** Problem 3: Corral the Cows [Marcello Herreshoff, 2005] Farmer John wishes to build a corral for his cows. Being finicky beasts, they demand that the corral be square and that the corral contain at least C (1 <= C <= 500) clover fields for afternoon treats. The corral's edges must be parallel to the X,Y axes. FJ's land contains a total of N (C <= N <= 500) clover fields, each a block of size 1 x 1 and located at with its lower left corner at integer X and Y coordinates each in the range 1..10,000. Sometimes more than one clover field grows at the same location; such a field would have its location appear twice (or more) in the input. A corral surrounds a clover field if the field is entirely located inside the corral's borders. Help FJ by telling him the side length of the smallest square containing C clover fields. PROBLEM NAME: corral INPUT FORMAT: * Line 1: Two space-separated integers: C and N * Lines 2..N+1: Each line contains two space-separated integers that are the X,Y coordinates of a clover field. SAMPLE INPUT (file corral.in): 3 4 1 2 2 1 4 1 5 2 INPUT DETAILS: |* * | * * +------ OUTPUT FORMAT: * Line 1: A single line with a single integer that is length of one edge of the minimum size square that contains at least C clover fields. SAMPLE OUTPUT (file corral.out): 4 OUTPUT DETAILS: Below is one 4x4 solution (C's show most of the corral's area); many others exist. |CCCC |CCCC |*CCC* |C*C* +------ **********************************************************************