Problem J
Barisal Stadium
Input: Standard Input

Output: Standard Output

Time Limit: 2 Seconds

 

The BCCB (Bangladesh Cricket Control Board) has decided to build a new international cricket stadium in Barisal. It will be convex in shape unlike others. Floodlight will be placed outside the stadium so that play is possible under light. Each floodlight covers a particular part of the stadium. A side of the stadium is covered by a floodlight if the normal on the side makes an acute angle with the light rays.

In the above figure stadium ABCDEF can be covered by two different sets of lights. It takes certain cost to build each floodlight. There are several options to choose the set of lights. In this problem you will have to find the minimum cost to cover the stadium completely. A stadium is completely covered if all of its sides is covered by at least one floodlight.

 

Input 

Each input set starts with a positive integer N which denotes the number of sides in the stadium. It will be in the range between 3 to 30. In next few lines the coordinates of the vertices will be given in anticlockwise order. Next line will contain another integer M (1<=M<=1000) denoting the number of light positions. In next few lines there will be 3M integers in the format x y c where (x, y) is the coordinates of the position and c (a positive integer) is the cost to build the floodlight in that position. All light positions will be strictly outside the stadium. The absolute value of each coordinate will not exceed 10000 and the cost to build a floodlight will be at most 10000000.
Input is terminated by a case where N=0. This case should not be processed.

 

Output 

For each input set print in a line the minimum cost to build the floodlights. If it is not possible to cover the stadium completely, then print "Impossible.".

 

Sample Input                             Output for Sample Input

3
0 0
10 0
0 10
3
-1 -1 10
11 -1 10
-1 11 10
3
0 0
10 0
0 10
3
-1 -1 10
11 -1 10
-1 12 10
0
Impossible.

20

 


Problemsetter: Md. Kamruzzaman, Member of Elite Problemsetters' Panel

Special Thanks to Mohammad Sajjad Hossain (Alternate solution)

 
 

“While it may be uncommon to find TopCoder in a university course today, over time this may change. Time constrained contests are a great way to sharpen coding chops, and better coders produce much more reliable software. The Association for Computing Machinery (ACM) understands this--they've been doing competitions for thirty years. Perhaps it's time for mainstream academia to get with the program.”

 

-pmadden

 

Source: http://www.topcoder.com/?&t=features&c=feat_030104