国内企业手机网站建设,阿里云虚拟主机可以做两个网站,长沙百度快照优化排名,多语言版本网站转载自http://www.cnblogs.com/aiguona/p/7248311.html#xff01;#xff01; 关于极角排序#xff1a; 在平面内取一个定点O#xff0c;叫极点#xff0c;引一条射线Ox#xff0c;叫做极轴#xff0c;再选定一个长度单位和角度的正方向#xff08;通常取逆时针方向 关于极角排序 在平面内取一个定点O叫极点引一条射线Ox叫做极轴再选定一个长度单位和角度的正方向通常取逆时针方向。 对于平面内任何一点M用ρ表示线段OM的长度有时也用r表示θ表示从Ox到OM的角度ρ叫做点M的极径θ叫做点M的极角有序数对 (ρ,θ)就叫点M的极坐标。 那么给定平面上的一些点把它们按照一个选定的中心点排成顺逆时针。 极角排序常用的四种方法 在说四种方法之前给出一会用到的函数和存储点的结构体 struct point//存储点
{double x,y;
};double cross(double x1,double y1,double x2,double y2) //计算叉积
{return (x1*y2-x2*y1);
}double compare(point a,point b,point c)//计算极角
{return cross((b.x-a.x),(b.y-a.y),(c.x-a.x),(c.y-a.y));
} 方法1利用atan2函数按极角从小到大排序。 关于atan2()函数在C语言的math.h或C中的cmath中有两个求反正切的函数atan(double x)与atan2(double y,double x) 他们返回的值是弧度要转化为角度再自己处理下。 前者接受的是一个正切值直线的斜率得到夹角但是由于正切的规律性本可以有两个角度的但它却只返回一个因为atan的值域是从-90~90 也就是它只处理一四象限所以一般不用它。 第二个atan2(double y,double x) 其中y代表已知点的Y坐标同理x ,返回值是此点与远点连线与x轴正方向的夹角这样它就可以处理四个象限的任意情况了它的值域相应的也就是-180~180了 bool cmp1(point a,point b)
{if(atan2(a.y,a.x)!atan2(b.y,b.x))return atan2(a.y,a.x)atan2(b.y,b.x);else return a.xb.x;
} 方法2利用叉积按极角从小到大排序。 关于叉积叉积0是指两向量平行重合叉积0则向量a在向量b的顺时针方向粗略的理解为在a在b的下方叉积0则向量a在向量b的逆时针方向粗略的理解为在a在b的上方 bool cmp2(point a,point b)
{point c;//原点c.x 0;c.y 0;if(compare(c,a,b)0)//计算叉积函数在上面有介绍如果叉积相等按照X从小到大排序return a.xb.x;else return compare(c,a,b)0;
} 方法3先按象限从小到大排序 再按极角从小到大排序 int Quadrant(point a) //象限排序注意包含四个坐标轴
{if(a.x0a.y0) return 1;if(a.x0a.y0) return 2;if(a.x0a.y0) return 3;if(a.x0a.y0) return 4;
}bool cmp3(point a,point b) //先按象限从小到大排序 再按极角从小到大排序
{if(Quadrant(a)Quadrant(b))//返回值就是象限return cmp1(a,b);else Quadrant(a)Quadrant(b);
} 关于三种方法的比较 第三种方法按象限从小到大排序 再按极角从小到大排序是在有特殊需求的时候才会用到这里不做比较。 关于第一种方法利用atan2排序他和利用叉积排序的主要区别在精度和时间上。 具体对比时间相较于计算叉积利用atan2时间快这个时间会快一点记得做过一个题用atan2排序过了用叉积的T了 精度 atan2精度不如叉积高做过一个题用anat2因为精度问题WA了。 所以两种方法根据情况选择一种合适的使用。 补充 对于atan为何范围比较小tan函数的周期是pi如果你只给一个tan值a/b那么当然只能返回一个范围为[k,kpi]的数。在这里则是[-pi/2,pi/2]. 而如果你给了a,b两个数相当于给出了[0 2pi]范围内的一个坐标点自然可以获得这个点对应的角度。
