[CTSC2004] 最优切割

HURRICANE小组的成员最近去工厂实习，在实习的过程中遇到了这样的一个问题。即要在一个模板内，切割出一个零件。现已知模板和零件都是给定的凸多边形，且零件在模板中的位置已经固定。我们知道，对于零件来说，除相邻的两边外，任何两条边的延长线的交点都在模板之外。 由于工厂的加工条件所限，切割时，每一刀必须沿零件的某一条边所在的直线切下，把模板分成两部分，然后保留含有零件的一部分，再继续切割。现定义每一刀的费用为模板上切痕的长度。问如何选择切割顺序，才能使花费最少？

你的程序需要根据给定的输入，给出符合题意的输出： - 输入包括模板及零件的形状和坐标； - 你需要根据给出的输入，计算出把模板切割成为零件的最少花费； - 输出中只包括一个数，即最少的花费。

输入文件包括两个部分，分别描述模板和零件的形状及坐标： - 第一行为模板的顶点个数n（3≤ n≤ 2000）。下面的n行每行两个实数x，y（-1,000,000<x, y<1,000,000），为按逆时针方向给出模板顶点的坐标。 - 第n+2行为零件的顶点个数m（3≤ m≤ 2000）。下面的m行每行两个实数x，y（-1,000,000<x, y<1,000,000）为按逆时针方向给出的零件顶点的坐标。

输出文件中只需要包括一个整数，为最少花费四舍五入到整数后的值。

4
0 0
3 0
3 3
0 3
4
1 1
2 1
2 2
1 2

8

4
0 0
3 0
3 3
0 3
4
0 0
2 0
2 3
0 3

3