[SCOI2003] 切割多边形

题目描述

我们希望通过切割得到一个凸 $p$ 边形,$p\le 8$。 一开始的时候,你有一个 $n\times m$ 的矩形,即它的四角的坐标分别为 $(0,0), (0,m), (n,0), (n,m)$。每次,你可以选择一条直线把当前图形切割成两部分,保留其中一个部分(另一部分扔掉),切割线的长度为此直线在多边形内部的部分的长度。 求出最短的切割线总长度。 下面是一个例子,我们需要得到中间的多边形。 ![](https://cdn.luogu.com.cn/upload/pic/18468.png) 分别沿着直线 $1,2,3,4$ 进行切割即可,得到中间的四边形。

输入输出格式

输入格式


第一行有两个整数 $n,m\ (0 < n,m < 500)$。 第二行为一个整数 $p(3\le p\le 8)$,以下 $p$ 行每行为两个整数 $x, y(0 < x < n, 0 < y < m)$,为按顺时针给出的各顶点坐标。 数据保证多边形的是凸的,无三点共线,输入数据无错误。

输出格式


仅一行,为最短切割线的总长度,四舍五入到小数点后 $3$ 位。允许有 $0.001$ 的误差。

输入输出样例

输入样例 #1

100 100
4
80 80
70 30
20 20
20 80

输出样例 #1

312.575

说明

样例对应于图中给出的例子。