国境
   
　　小人国的国境是一个面积大于零的凸多边形，多边形的顶点被看成警戒塔。由于国境线狭长且维护费用昂贵的缘故，政府决定修改国境，使得它变短些。但是他们又不想建新的警戒塔，利用一些旧的警戒塔作为新的国境的一部分。

　　每天，边疆守卫都要巡视国境，警戒塔的编号为1，2，…，N。他们按顺时针方向从1号塔开始，一个一个警戒塔的巡视国境。例如图中（单位为公里）的国境，从1到2到3到4到5再到1总长为57.89公里。为了使国境线尽可能的短，则新的国境可以是2-3-4-2，总长度减少到27.31公里。但是，小人国中有一些历史纪念碑，它们是国家的主面象征。这些纪念碑必须不息一切代价地被保留下来。

　　　　　　　　　　　

　　你的任务是确定最短国境，使得新的国境内包含所有的历史纪念碑。在例图中A、B就是两座纪念碑，为了确保新的国境包含它们，最短的国境是1-2-3-4-1，总长51.78公里。

　　输入

　　输入文件的第一行包含两个整数N和M，N（ 3≤ N≤50）是小人国国境上的警戒塔的数目，M (0 ≤M≤ 1000)是历史纪念碑的总的数目。接下来N行为顺时针方向的N个警戒塔的坐标，然后M行为历史纪念碑的坐标。所有的坐标都是绝对值不超过10000的整数。所有的警戒塔位置都互不相同。

　　输出

　　输出文件仅包含一个实数，为最短的新国境长度（单位为公里，且保留两位小数）。

　　Sample input #1

　　5 0
　　8 9
　　0 -7
　　-8 -7
　　-8 1
　　-8 9

　　Output for the sample input #1

　　27.31

　　Sample input #2

　　5 2
　　8 9
　　0 -7
　　-8 -7
　　-8 1
　　-8 9
　　-4 -3
　　-1 -5

　　Output for the sample input #2

　　51.78
　　 		   

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有