#P1390. [CEOI2008]Fence

    ID: 402 传统题 1000ms 512MiB 尝试: 323 已通过: 118 难度: 8 上传者: 标签>CF2400提高+/省选-凸包Andrew 算法点在多边形内方向判定Floyd–Warshall

[CEOI2008]Fence

[CEOI2008] Fence

题目描述

在一个大小为 1000×10001000\times 1000 的区域中,有 nn 个固定点, mm 棵树 。

现在你要建一个围栏来保护树,建它的费用为你选用的固定点的个数 ×20\times 20 +你没有圈进围栏的树 ×111\times 111。

现在希望这个值越小越好,求最小值。

输入格式

第一行给出 n,mn,m。

接下来的 nn 行,给出固定的坐标。

接下来的 mm 行,给出树的坐标。

输出格式

输出最小费用。

样例 #1

样例输入 #1

4 3
800 300
200 200
200 700
600 700
400 300
600 500
800 900

样例输出 #1

171

提示

对于 100%100\% 的数据,3≤N≤1003\le N\le100,1≤M≤1001\le M\le100,所有坐标均为 [0,1000][0,1000] 中的整数。所有固定点和树的位置两两不同,并且其中任意三个位置不共线。可以选择不修围栏。


样例解释: