506 . Amritapuri
Description
Amrita is indeed a good place to walk, to go around, and to host a contest, but there are some big problems outside this beautiful campus.
Recently Amrita campus is "concerned" by some hackers from Mumbai. These hackers claimed that they were going to step in some very important programming contests - like ACM-ICPC regionals, and give a "No - Snack Limit Exceeded" response to every submission during the contest. Moreover, the website of the contest will be changed into some book covering of G.B. Hwang. These are the things you never want to see =D
Therefore, it is the time to stand out to protect this good place at all costs.
But first, you must be willing to see what you can do.
After surveying every place in campus, it is concluded that there are some "hot spots" those hackers would be possibly hiding in, and of course, waiting for the perfect moment to attack. Thus you need some watching towers and some wires to keep the communications between towers.
Those towers and wires hence formed a closed watching area. All "hot spots" enclosed in the area will be safely protected. But the "hot spots" outside the area will be fully hacked and you'll cost $91 million Rupees each, for repairing those devices in "hot spots".
Moreover, things are not always as good as you think, in order to keep the effective defending power, you need $19 million Rs each for constructing a fully powered watching tower, and these towers can only be build in some pre-decided places on the map. The wires connecting two watching towers must be a straight line so that the communication between two towers can be fast. Wires are costless, so the tower building company provides you with any length as long as you want.
So, the main problem is, what is the minimum cost for this defense action?
For example, there are 3 "hot spots" in the campus denoted by a small square in the figure below, and 4 possible positions for building a watching tower presented as small circles. Choose the three filled circle and the two "hot spots" is under watching. The total cost is 3*$19 + 1*$91 = 148 million Rs.
Input Format
Input data contains one or more than one test cases. The first line of each test case contains two integers N and M (3 ≤ N ≤ 100, 1 ≤ M ≤ 100). N is the number of pre-decided points for placing towers, and M is the number of "hot spots". This line is followed by N lines that describe
the positions, and then by M lines that describe the positions of the "hot spots". All
positions are given as pairs of integers x y on one line (0 ≤ x, y ≤ 1 000). You can expect that no two positions coincide and that no three positions are collinear.
Output Format
Output the minimum cost.
Sample Input 1
4 3 800 300 200 200 200 700 600 700 400 300 600 500 800 900
Sample Output 1
148
Hints
This example corresponds to the picture above.
Problem Source
Migrated from old NTUJ.
DarkTmt, Adapted from CEOI2008, fence
Subtasks
| No. | Testdata Range | Score |
|---|