【bzoj1185】[HNOI2007]最小矩形覆盖

2014年12月24日3,7527

Description

题解

首先有一个结论,矩形的一条边一定在凸包上!!!
枚举凸包上的边
用旋转卡壳在凸包上找矩形另外三点。。。
注意精度问题

 

 

  • 张凯羿2014年12月24日 下午8:47 回复

    高亮没了

    #1  
    • 张凯羿2014年12月24日 下午8:48 回复

      哦……是我的网速太渣了 = = 、

      #11
  • 罗崚骁2015年12月2日 上午8:22 回复

    敢问有一条边必在凸包上这个结论如何证明……

    #2  
    • hzwer2015年12月2日 下午9:23 回复
      admin

      思考了一下,我只会证明三角形

      #21
      • 罗崚骁2015年12月3日 下午10:24 回复

        能证三角形的话……试一下归纳法?QWQ

        #22
        • BPM1362015年12月6日 下午12:55 回复

          其实大概脑补了下证明是这样的,因为我们首先可以很轻易的想到必然有一个点在矩形上否则必然不是最优解,然后因为如果只有一点在矩形上,那我们可以收缩这个矩形至凸包上两个点都在矩形上,这时候有两种情况,一种是对角线,一种是相邻的两个点(于是就不加以讨论),因为这是一个矩形,所以对角线一定比边要长,所以当对角线在矩形上时,我们假设这个矩形的一边长度已经固定(实际上这个长度就是我们卡左右两点的长度),因为这是一个凸包,所以旋转时不可能有除了当前枚举点左右相邻点之外的点落在矩形上,否则左右相邻点必然不在这个矩形内,然而旋转的时候高(也就是到对称点的距离)的长度是一个单峰函数,它在相邻两点都在矩形上时取到最小值(凸包的对顶点性质),而这两点吧必然构成这个矩形一边否则我们可以旋转使它其中两个点落在矩形上,然后相同思考方法即可,主要就是要去掉我们卡左右点时的影响,证明的时候把这个矩形的底长看成是固定的然后再证就简单多了

          #23
        • BPM1362015年12月6日 下午12:57 回复

          只是只弱菜错了求轻喷别太重QAQ

          #23