#P2381. patrol

patrol

题目描述

城市中有 nn 个需要夜间巡逻的地点。巡逻员 ZY 和小 Y 各负责一个凸多边形区域,区域可以退化成线段或单点。两个区域严格不相交,且二者合起来必须覆盖全部 nn 个地点。

ZY 让小 Y 决定区域的具体边界,但不接受自己负责的区域面积大于小 Y 的方案。求在这些条件下小 Y 负责的区域的最小面积。

输入格式

第一行一个整数 nn(1≤n≤501\le n\le50)。

第二行 nn 个整数,为各点的横坐标。第三行 nn 个整数,为对应点的纵坐标。每个坐标的绝对值不超过 10001000。

输出格式

输出小 Y 所负责区域的最小可行面积,保留一位小数。

样例

5
-1000 -1000 1000 1000 0
-1000 1000 -1000 1000 0
1000000.0

一种最优方案是让 ZY 负责 (−1000,−1000),(−1000,1000)(-1000,-1000),(-1000,1000),面积为 00。让小 Y 负责 (1000,−1000),(1000,1000),(0,0)(1000,-1000),(1000,1000),(0,0),面积为 10000001000000。

数据范围

对于 30%30\% 的数据,n≤15n\le15。对于所有数据,n≤50n\le50。

原 PDF 题面