[CTSC2004]最优切割

时间限制:10s      空间限制:162MB

题目描述

HURRICANE小组的成员最近去工厂实习,在实习的过程中遇到了这样的一个问题。即要在一个模板内,切割出一个零件。现已知模板和零件都是给定凸多边形,且零件在模板中的位置已经固定。且我们知道,对于零件来说,除相邻的两边外,任何两条边的延长线的交点都在模板之外。由于工厂的加工条件所限,切割时,每一刀必须沿零件的某一条边所在的直线切下,把模板分成两部分,然后保留含有零件的一部分,再继续切割。现定义每一刀的费用为模板上切痕的长度。问如何选择切割顺序,才能使花费最少?【任务描述】你的程序需要根据给定的输入,给出符合题意的输出: 输入包括模板及零件的形状和坐标; 你需要根据给出的输入,计算出把模板切割成为零件的最少花费; 输出中只包括一个数,即最少的花费。


输入格式

输入文件包括两个部分,分别描述模板和零件的形状及坐标:第一行为模板的顶点个数n(3≤ n≤ 2000)。下面的n行每行两个实数x,y(-1*10^10


输出格式

一个实数,精确到个位,表示最少花费。


样例输入

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

样例输出

8

提示

没有写明提示


题目来源

没有写明来源