Cross-Country Orienteering, one of more and more important and well-known sports games in Hunan University, has made the University more and more impressive in the National competitions. Each year,after the military training there will be a Cross-Country Orienteering for the freshmen.
The form of the orienteering is Score Orienteering,Many controls are placed throughout the area, each having a point value determined by its distance from the start/finish or its technical difficulty. Participants have a set time to find as many controls as they can and earn as large a point value as possible. There is a large point penalty for being over-time. Highest score wins!
To win the game,you should find all the controls.If you can compute the best route by compute programing, you will have great advantages.Now give you the map,the map contains the start location,end location,all the controls location,and the obstruction,obviously you can’t cross the obstruction.To simple the problem,you can assume that the obstruction is a polygon which has not got self-intersections or self-contacts. And all the control and start,end point are outside the obstruction.Can you find the minimum length way from start point to end point and cross all the controls.Why not try?!
The first line in the input is one integer T, indicates the number of test cases. Each test case begin with two integers n(n<=100) the number of vertices of the polygon, m(m<=10) the number of the controls,the second line is four integers(x1,y1,x2,y2),these integers represent the start and end point .then followed n lines,each line is the vertices coordinate,in counterclockwise order. and the next is m lines,each line is the coordinate of the control.All the coordinates are integers and the value less than 100000.
The output consists of one line containing the length of a shortest way, with the accuracy 0.01.