浅谈极角排序

Posted on | Edited on | In | Views:

前言

博主原先对于计算几何可谓是一窍不通，刚好做到两道极角排序的题，才刚刚有点感受到计算几何的魅(e)力(xin)。

极角排序

所谓极角，指的就是以x轴正半轴为始边，逆时针转过的角，这个角的范围是$[0,2\pi]$。

极角排序的求法

利用atan2函数

atan2(y,x)，表示(x,y)这个点与原点连线，这条线与x轴正半轴的夹角，这里的这个极角的范围是$[-\pi,\pi]$的，一二象限为正，三四象限为负。所以我们从小到大排完序后，实际上是第三象限$\to$第四象限$\to$第一象限$\to$第二象限。

1
2
3
4
5
6
7
8
9
10
11
12
struct node{
    int x,y;
    double angle;
    inline bool operator < (const node &t) const{
        return angle<t.angle;
    }
}
for (int i=1;i<=n;i++){
    read(a[i].x),read(a[i].y);
    a[i].angle=atan2(a[i].y,a[i].x);
}
sort(a+1,a+n+1,cmp);

利用叉积来进行排序

叉积

已知两点坐标，通过叉积可以求得与原点所围成的三角形的有向面积。
比如这两个点为a,b.
$\frac{1}{2}*(a.x*b.y-a.y*b.x)$即为该三角形面积，那么为什么说是有向面积呢，如果这个值是正的，说明b位于a的正方向，即逆时针方向(当然，这个角度小于$\pi$)，反之，如果这个面积是负的，说明b位于a的负方向，即顺时针方向。
那么我们就可以通过叉积来求极角了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct node{
    int x,y;
    double angle;
    inline int operator * (const node &t) const{
        return a.x*b.y-a.y*b.x;
    } 
}
inline bool cmp(node a,node b){
    return a*b>0;
}
for (int i=1;i<=n;i++){
    read(a[i].x),read(a[i].y);
}
sort(a+1,a+n+1,cmp);

比较两种求法的优劣

第一种求法的常数比较优秀，但是精度有一定的损失。而叉积的求法常数较大，但是没有精度损失，可以根据情况的不同进行选择。

例题

1.Luogu 2992
题目大意：给你平面上n个点，保证任意两个点的连线都不经过原点，我们称所有包括原点的三角形为黄金三角形，问有多少个黄金三角形。
$n\le100000$
直接求黄金三角形好像有点难，我们考虑算出所有三角形的数量去减去非黄金三角形的数量。
所有三角形的数量组合数算出。
对于非黄金三角形，先确定一个点a，如果另外两个点均在我正方向$\pi$内，那么这三个点一定能构成一个非黄金三角形，如果不能理解的话可以画个图。
我们先将所有的点极角排序，那么就可以一个指针扫过去知道有多少个点是在这个范围内的，组合数计算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
using namespace std;
int n,tot,r;
LL ans;
struct node{
	int x,y;
	long double angle;
}a[N]; 
inline bool cmp(node a,node b){
	return a.angle<b.angle;
}
template <typename T> void read(T&t) {
	t=0;
	bool fl=true;
	char p=getchar();
	while (!isdigit(p)) {
		if (p=='-') fl=false;
		p=getchar();
	}
	do {
		(t*=10)+=p-48;p=getchar();
	}while (isdigit(p));
	if (!fl) t=-t;
}
inline bool cj(int x,int y){
	return 1ll*a[x].x*a[y].y>=1ll*a[x].y*a[y].x;//逆时针旋转小于pi 
}
int main(){
	read(n);
	for (int i=1;i<=n;i++) read(a[i].x),read(a[i].y),a[i].angle=atan2(a[i].y,a[i].x);
	sort(a+1,a+n+1,cmp);
	r=2;
	for (int i=1;i<=n;i++){
		while (r!=i&&cj(i,r)) tot++,r=r%n+1;
		ans-=1ll*tot*(tot-1)/2;
		tot--;
	} 
	ans+=1ll*n*(n-1)*(n-2)/6;
	printf("%lld",ans);
	return 0;
}

2.Luogu3476
题目大意：给定平面上n个位于第一象限的点，求这些点所能组成的三角形的面积和。
$0\le n\le3000$
三个点不好处理，数据范围又是可以跑$n^2$的，考虑先枚举一个点，计算所有在它右边的点与它组成三角形的面积。
先将所有点按照x坐标排序，如果x坐标相同则按y排序，枚举一个点，再将在我右侧的点极角排序。
从小到大扫过去，那么叉积所得的值就一定是正的了，再将叉积展开，就可以得到一个后缀和的形式了，预处理一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (3005)
using namespace std;
template <typename T> void read(T&t) {
	t=0;
	bool fl=true;
	char p=getchar();
	while (!isdigit(p)) {
		if (p=='-') fl=false;
		p=getchar();
	}
	do {
		(t*=10)+=p-48;p=getchar();
	}while (isdigit(p));
	if (!fl) t=-t;
}
int n,tot;
LL sumx,sumy,ans;
struct node{
	int x,y;
}a[N],q[N]; 
inline bool cmp(node a,node b){
	return a.x==b.x?a.y<b.y:a.x<b.x;
}
inline bool cmp1(node a,node b){
	return 1ll*a.x*b.y-1ll*a.y*b.x>0;
}
int main(){
	read(n);
	for (int i=1;i<=n;i++){
		read(a[i].x),read(a[i].y); 
	}
	sort(a+1,a+n+1,cmp);
	for (int i=1;i<=n;i++){
		tot=0;
		for (int j=i+1;j<=n;j++){
			tot++;
			q[tot].x=a[j].x-a[i].x;
			q[tot].y=a[j].y-a[i].y;
		}
		sort(q+1,q+tot+1,cmp1);
		sumx=0,sumy=0;
		for (int j=1;j<=tot;j++) sumx+=q[j].x,sumy+=q[j].y;
		for (int j=1;j<=tot;j++){
			sumx-=q[j].x,sumy-=q[j].y;
			ans+=sumy*q[j].x-sumx*q[j].y;
		}
	}
	printf("%lld.%lld",ans/2,(ans&1)*5);
	return 0;
}

结语

简单的讲解了一下极角排序，希望能够有所帮助。