【bzoj3707】【FJ2014集训】圈地

2014年8月31日2,3363

【题目描述】

2维平面上有n个木桩,黄学长有一次圈地的机会并得到圈到的土地,为了体现他的高风亮节,他要使他圈到的土地面积尽量小。圈地需要圈一个至少3个点的多边形,多边形的顶点就是一个木桩,圈得的土地就是这个多边形内部的土地。(因为黄学长非常的神,所以他允许圈出的第n点共线,那样面积算0)

【输入格式】

第一行一个整数n,表示木桩个数。
接下来n行,每行2个整数表示一个木桩的坐标,坐标两两不同。

【输出格式】

仅一行,表示最小圈得的土地面积,保留2位小数。

【样例输入】

样例1:
3

0 0

0 1

1 0

样例2:
4

0 0

0 1

0 2

1 1

【样例输出】

样例1:
0.50
样例2:
0.00
【数据范围】

对于10%的数据,n<=100;
对于30%的数据,n<=300;
对于50%的数据,n<=500;
对于100%的数据,n<=1000。

2014.8.19

先暴个力。。。

出题人题解:

显然,这时候暴力枚举会T。于是我们转变一下思路,如果我们确定了2个点以后,第三个点有必要去盲目的枚举吗?答案是否定的。实际上我们把经过这两点的线看成一个斜率,把他当成y轴你会发现第三个点明显是在坐标系左右找一个离”y轴”最近的点来算面积更新答案。然后我们可以继续思考,发现我们可以把点按照某个斜率当成”y轴”进行“从左到右”的排序,这样当2点共线的时候,用这两个点的左右2个点去更新答案就好了。也就是说我们采用旋转坐标系的方法,一开始按x坐标排好序,认为直接用竖着的那条斜率,然后维护的话每次其实当两点共线后只要交换他们就能得到斜率转过该事件点的序列。所以我们可以预处理出所有可行的斜率,当成事件点,不断转动坐标系更新答案就好。这样复杂度只有n^2,期望得分100.(这确实只是个暴力的优化 啊。。。不要砸我T_T)

以上我不会写T T

wjy神犇提供了一种乱搞的做法T T

好像非常厉害

按照x坐标排序,将相邻的点分为一块,块内暴力。。

由于这样不够靠谱,所以我们随机旋转坐标系几十次就差不多了

2014.8.31

来补正解了

 

 

  • 章可循2016年2月11日 下午7:20 回复

    斜率直接除不会有0的情况吗?

    #1  
    • hzwer2016年2月16日 下午2:40 回复
      admin

      double类型除0不会出事的0.0

      #11
  • gzz2017年3月23日 下午6:20 回复

    我有O(n^2log^2n)的做法哦~跑了6s。。
    思路完全不同。。枚举一个点,保留右侧点,CDQ分治+凸包优化。。

    #2