【BZOJ3571】【HNOI2014】画框

久闻公之大名

大概就是 把每个结果看成坐标为\(\sum a,\sum b\)的点,那么答案一定在这些点的左下凸壳上。

为了勾勒出凸包,我们可以先找到最左边和最下面的两个点,然后每次找到离当前两个点连线最远的点并分两边递归向下。

要找到最远的点,只要算出每个\(a,b\)的截距,那么只要截距最小即可。这个可以用KM算法来求。

说点什么

您将是第一位评论人!

提醒
wpDiscuz