wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
bzoj1069 最大土地面积 O(nlogn+n)
? 计算几何 ?
2017-03-19 20:00:04
275
0
0
wuvin
? 计算几何 ?
##Description 在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成的多边形面积最大。 ##Input 第1行一个正整数N，接下来N行，每行2个数x,y，表示该点的横坐标和纵坐标。 ##Output 最大的多边形面积，答案精确到小数点后3位。 ##Sample Input 5 0 0 1 0 1 1 0 1 0.5 0.5 ##Sample Output 1.000 ##HINT 数据范围 $n \le 2000 , |x|,|y| \le 100000$ 今天上午考到这个原题，比较懒不想讨论凹四边形就写了个n^2logn，就T飞了，YZ和LCR的n^2由于常数大也T了。（测评机。。。） 三角形最大面积可以$O(n)$,所以花了半小时尝试推广到四边形，但始终没有成功，正确性很玄学啊。不过途中不小心搞出了另外一种$O(n)$的做法。 最大面积的四边形首先求个凸包不用说，nlogn。这是最大的复杂度了，后面就$O(n)$了。如果是凹的，那么凸包上一定只有三个点，另外一个枚举就是了$O(n)$。接下来是凸的情况。 先分析答案，有 ###推论一 最大面积四边形一定由两个对踵点对组成，不然就可以通过固定一条对角线改变一个点来扩大面积。 ##推论二 这两个对踵点对是一一对应的。因为知道一个可以求另一个。 所以我们可以通过旋转卡壳来枚举一对对踵点对，而由于另对的顺序也是单调的，所以也只用转一圈。所以复杂度就是旋转卡壳的复杂度$O(n)$。
上一篇:
7.5集训总结
下一篇:
Apio酱油记
0
赞
275 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
wuvin
没有帐号? 立即注册