다수의 점들을 각도에 따라 정렬하기

 

* 무엇을 위한 것인가?

 

백준 1708번 - 볼록 껍질을 편하게 풀기 위한 사전 지식용으로 써봤다.

 

컨벡스 헐 (Graham's Scan) 을 이용하기 위해서는 좌표 위의 점들을 각도에 따라 정렬해야한다.

 

그에 대한 내용을 모두 포함하여 1708번 문제의 해설로 적기에는 너무 길어질 것 같아

 

따로 글을 분리하여 서술하기로 했다.

 

 

그리고 수학을 너무 많이 까먹어서 리마인드용이기도 하다.

 

 

 

 

벡터곱 (Cross Product)

 

고등학교 교육 과정에서는 벡터곱 = 외적이라고 하지만,

 

엄연히 벡터곱 (Cross Product) ≠ 외적 (Outer Product) 이라는 것을 잊지 말자.

 

또한 설명의 간소화를 위해 3차원 벡터의 연산으로 나타내었다.

 

 

 

i, j, k 는 각각 x, y, z 방향에 대한 단위 벡터이다.

 

 

2차원에서의 벡터곱

 

인터넷에서 2차원에서의 벡터곱을 찾아보면, 그 결과가 벡터가 아닌 스칼라의 형태로 나와있는 경우가 있다.

 

따지고 보면 잘못된 결과값으로, 다소 오해를 불러일으킬 소지가 있다고 생각된다.

 

 

 

일단은 2차원에서 벡터곱을 구하는 방법은 위의 식에서 z 좌표값을 0으로 두고 계산하면 된다.

 

 

벡터곱의 결과값에서 z만 0이 아닐 수 있게 된다.

 

많은 글에서 이 결과값의 z값만을 표기하는 경우가 많아

 

벡터가 결과로 나와야할 벡터곱에서 스칼라가 나와 혼란을 일으키는 경우가 많았던 것이다.

 

물론 이 z값만이 결국 의미가 있는 유일한 요소이긴 하다.

 

 

 

 

벡터곱의 결과값(z)의 의미

 

이젠 z값(앞으로 계속 z로 표기)만 어떻게 이용할지 설명하면 끝이 나겠다.

 

오른손 법칙을 이용해서 중지가 나를 향하면 z가 양수다. (規)

 

z 가 음수면 시계방향 ( u → v ),

z 가 양수면 반시계방향,

z 가 0이면 일직선 상 (180º 도 가능) 에 위치한다.

 

 

 

 

이제 코드로 짜보자

 

고려할 것 3개만 생각해놓자.

 

1. 원점을 어떻게 할 것인가

2. 시작점은? (정렬했을 때 가장 먼저 놓을 것은?, 그에 따른 정렬 기준은?)

3. 일직선 상(같은 각, 180º)에 있는 애들은 어떤 순으로 놓을 것인가 

 

 

사람마다 다르게 설정해도 상관은 없는데

 

나는 다음과 같이 정했다.

 

1. 원점은 과감히 제외한다. (zero로 원점이 있다는 것을 확인. 굳이 출력 안 함)

2. x축의 양수 방향에서 시작해서 반시계 방향으로 돌리기.
    그래서 y값이 양수인 애들끼리, 음수인 애들끼리 벡터곱. 다르면 y가 양수인 애들이 앞으로.

3. 반대방향의 경우 y가 양수인 애들이 앞으로(그래야 2번에 맞출 수 있다.), 같은 방향은 거리가 짧은 애를 앞으로

 

 

 

내 코드

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;

struct D{
	ll x,y;
};
bool cmp(D a,D b){
	if(a.y==0&&b.y==0) {
		if(a.x*b.x<0) return a.x>b.x;
		return abs(a.x)<abs(b.x);
	}
	if((a.y>=0&&b.y<0)||(b.y>=0&&a.y<0)) return a.y>b.y;
	ll z=a.x*b.y-a.y*b.x;
	if(z>0) return 1;
	if(z<0) return 0;
	return abs(a.x)+abs(a.y)<abs(b.x)+abs(b.y);
}
D d[100010];
int zero=0;
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++) {
		scanf("%lld %lld",&d[i].x,&d[i].y);
		if(d[i].x==0&&d[i].y==0) i--,n--,zero=1;
	}
	sort(d,d+n,cmp);
	for(int i=0;i<n;i++) {
		printf("%d : %lld %lld\n",i,d[i].x,d[i].y);
	}
}

테스트 케이스

25
0 0
3 0
-6 0
2 1
0 3
1 -2
2 -4
2 -1
1 2
-2 4
-1 2
-2 -4
0 -3
0 -6
-3 0
-2 -1
-4 -2
-2 1
-4 2
0 6
4 2
6 0
2 4
-1 -2
4 -2

결과

3 0
6 0
2 1
4 2
1 2
2 4
0 3
0 6
-1 2
-2 4
-2 1
-4 2
-3 0
-6 0
-2 -1
-4 -2
-1 -2
-2 -4
0 -3
0 -6
1 -2
2 -4
2 -1
4 -2

 

 

특별히 코드를 더 다듬지는 않았다. 어쩌면 일부 케이스에 대해 틀린 답을 내놓을 수도 있다.

 

줄인다면 더 줄일 수는 있겠지만...    귀찮다.....