DWITE '07 R3 #4 - The Convex Fence Company

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 64M

Problem type
DWITE Online Computer Programming Contest, December 2007, Problem 4

The world renowned mathematician, Dr. J.R.R "Bob" Dobbs, has collected rocks for years, and has built up quite a substantial collection, which he keeps scattered throughout his backyard. Unfortunately, after an interview with the local newspaper, thieves have been trying to steal his precious stones, and so Dr. Dobbs has called the Convex Fence Company to build a fence around them for him.

His instructions to the Convex Fence Company were very precise. Being very proud of his collection, he's instructed that the Convex Fence Company make sure that no matter where he's standing in his yard, the fence doesn't block the view. Below is an example of a possible fence.

A happy Mr. Dobbs

The above fence has five sections. The Convex Fence Company sells their fence by the meter, and so charges the client for a full meter even if they only use a portion of one for a section. That is to say, if the above sections were 4.3m, 4.9m, 2.6m, 5.1m and 1.8m long, the Convex Fence Company would charge them for 5m, 5m, 3m, 6m and 2m for a total of 21m of fencing – even though they really only used 18.7m of fence (the real thieves are made known!)

Given that fence costs m dollars per meter, what is the minimum that such a setup will cost? Note that sections of the fence can only be built in a straight line, and assume that rocks take up only a point.

The following format will be repeated five times within the file, each time describing a different setup of rocks in Mr. Dobbs' backyard:
Line 1: Positive integer R \le 1000, the number of rocks in Mr. Dobbs' collection.
Line 2: Positive integer m \le 50, the cost in dollars per meter of fence.
Line 3 to 3+R: Positive integer X, followed by a space, followed by positive integer Y, representing the location of one of Dobbs' rocks (coordinates given in meters). (X, Y) \le (1000,1000)

The output will contain 5 lines, a formatted string per line — the cost to fence Mr. Dobbs' rocks.

Note: the formatted string for the output is in the form $abc.00.

Sample Input

4
5
1 1
4 1
1 4
2 2

Sample Output

$55.00

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments


  • 7
    glasa  commented on March 7, 2021, 5:29 a.m. edit 2

    In case anyone else is having the trouble I had with R = 1 and R = 2. If R = 1 the answer is $0.00 and if R = 2 the answer is 2 times the distance between the two points. Don't think that sharing this information violates any rules and the question failed to specify for those cases.