标签 - 计算几何

? 计算几何 ?    2017-03-19 20:00:04    178    0    0

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

数据范围 n2000,|x|,|y|100000

今天上午考到这个原题,比较懒不想讨论凹四边形就写了个n^2logn,就T飞了,YZ和LCR的n^2由于常数大也T了。(测评机。。。)

三角形最大面积可以O(n),所以花了半小时尝试推广到四边形,但始终没有成功,正确性很玄学啊。不过途中不小心搞出了另外一种O(n)的做法。

最大面积的四边形首先求个凸包不用说,nlogn。这是最大的复杂度了,后面就O(n)了。如果是凹的,那么凸包上一定只有三个点,另外一个枚举就是了O(n)。接下来是凸的情况。

先分析答案,有

推论一

最大面积四边形一定由两个对踵点对组成,不然就可以通过固定一条对角线改变一个点来扩大面积。

? 知识点 ? ? 计算几何 ?    2017-03-19 19:23:51    684    1    0

快省选滚粗了,来总结一下计算几何

计算几何是著名的口上A着快,写出来各种拿不到分,大坑小坑满天飞(做过的所有计算几何题只有两道1A了。所有计算几何几乎没法调试,没法对拍)。

所以在这里总结一下类型,先从基础讲起。信息学的几何和数学的几何有很大不同,由于有强大的计算能力所以一般直接爆算就是了,什么梅尼劳斯、费马点之类的公式完全用不上,暴力不解释。由于要解析几何,使用向量特别多,比如空间中一条直线,能用向量两点式就不用y=kx+b,为什么?k计算时会爆啊inf...,暴了就WA了。

向量的使用有极大的优势,可以不用区分象限什么的,面积叉积就好了,由于有了向量,什么距离面积都可以是负的,极大地统一了公式尽量免去了分类讨论与细节。


叉积

不支持交换律,A×B=a.x*b.y-b.x*a.y,就是由ABO所形成的三角形的面积的两倍(B在OA左侧为正,反之为负),至于证明。。。网上多的是。用来判断直线与点的位置关系用得最多。比如poj2318。用来求面积也有,比如bzoj1132。

极角

也就是向量与X轴正方向的夹角,这个可比数学好用多了,比如两角之和的cos值怎么求?和角公式?直接暴力atan2、acos、asin求出角度相减就是,然后再求一个cos,这时终于感到cmath库的强大了。例:bzoj1419.

向量旋转

可以如上方所述暴力,但暴力较慢,如果旋转操作特别多的话还是手推和差角公式转一转。练习题目poj3845。还有一道旋转玄学bzoj3707。(顺带附上一句bzoj3707的方法在有三点共线的情况下是错的别问我是怎么知道的,不过此题不影响,反正是0,只是这个方法不能用来求最大三角形面积。)

直线相交

向量两点式配合面积倒一倒来求交点还是很兹糍的,草稿纸上手玩一下就好了,不过要考虑到特殊情况才行。比如这几种情况

  1. inline point get_inter(const seg &a,const seg &b){
  2. long double p1=-cross(dec(a.b,a.a),dec(b.b,a.a));
  3. long double p2=cross(dec(a.b,a.a),dec(b.a