각도 정렬 (Angle Sorting / Polar Sort) 은 2차원 평면 위의 점들을 기준점에 대한 극각 (polar angle) 순서로 정렬하는 기법. atan2 함수를 이용한 실수 비교 또는 CCW (외적) 를 이용한 정수 비교로 구현. 컨벡스 헐의 Graham scan, 점들을 단순 다각형으로 연결하는 문제 등에서 핵심 구성 요소.
문제 상황과 동기
N 개의 점을 기준점 O 를 기준으로 반시계 방향 (또는 시계 방향)으로 정렬해야 할 때.
Naive (atan2): 각 점에 대해 atan2(y, x) 를 계산해 실수 키로 정렬. O(N log N). 간단하지만 부동소수점 오차와 사분면 경계 처리 필요.
CCW comparator: ccw(O, a, b) > 0 만으로 정렬. 모든 연산이 정수. strict weak ordering 을 만족시키려면 사분면 구분이 필수.
핵심 통찰: 기준점 O 를 기준으로 점들을 반평면 (upper/lower) 으로 나누고, 같은 반평면 내에서만 CCW 비교 하면 strict weak ordering 이 성립하며, atan2 없이 정수 연산만으로 정확한 각도 정렬이 가능.
시각화
핵심 아이디어
atan2 방식
sort by atan2(y - O.y, x - O.x)장점: 직관적, 구현 단순단점: double 오차, atan2 비용, inf/nan 처리
CCW comparator 방식
bool cmp(a, b): // 1. 사분면이 다르면 사분면 기준 정렬 if quadrant(a) != quadrant(b): return quadrant(a) < quadrant(b) // 2. 같은 사분면이면 CCW if ccw(O, a, b) != 0: return ccw(O, a, b) > 0 // 3. 각도가 같으면 거리순 return dist(O, a) < dist(O, b)
사분면 판정
quadrant(p): if p.y == 0 and p.x >= 0: return 0 // +x축 if p.y > 0 or (p.y == 0 and p.x < 0): return 1 // upper half return 2 // lower half (including -x axis and negative y)
또는 구사과의 관용 코드:
if (half(a) != half(b)) return half(a) < half(b)if (ccw(a, b) != 0) return ccw(a, b) > 0return dist2(a) < dist2(b)
여기서 half(p) = (p.y > 0) or (p.y == 0 and p.x < 0).
알고리즘
INPUT: points P[0..N-1], origin O (default 0,0)OUTPUT: P sorted by polar angle (CCW)1. 각 점 P[i] 에 대해 quadrant = half(P[i] - O) 계산2. sort P by key: a. quadrant first (upper half < lower half) b. if same quadrant: ccw(O, a, b) > 0 (반시계 우선) c. if collinear: euclidean distance squared ascending
구현
// CCW 기반 각도 정렬 (구사과 스타일)#include <bits/stdc++.h>using namespace std;using ll = long long;struct Point { ll x, y; };int ccw(Point a, Point b, Point c) { ll ret = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); if (ret > 0) return 1; if (ret < 0) return -1; return 0;}ll dist2(Point a, Point b) { ll dx = a.x - b.x, dy = a.y - b.y; return dx * dx + dy * dy;}// upper half = y>0 or (y==0 && x<0)bool half(Point p) { return p.y > 0 || (p.y == 0 && p.x < 0);}int main() { int n; cin >> n; vector<Point> P(n); for (auto& p : P) cin >> p.x >> p.y; Point O = P[0]; // 기준점 (보통 최하단 좌측) // O 가 첫 원소가 되도록 swap 한 후 나머지만 정렬 // 여기서는 O 를 기준으로 모두 정렬 sort(P.begin(), P.end(), [&](Point a, Point b) { if (half(a) != half(b)) return half(a) > half(b); if (ccw(O, a, b) != 0) return ccw(O, a, b) > 0; return dist2(O, a) < dist2(O, b); }); for (auto& p : P) cout << p.x << " " << p.y << "\n";}
# 각도 정렬 (CCW comparator)import sysfrom functools import cmp_to_keyinput = sys.stdin.readlinedef ccw(ax, ay, bx, by, cx, cy): return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)def half(x, y): return y > 0 or (y == 0 and x < 0)def angle_cmp(O): ox, oy = O def cmp(a, b): ax, ay = a; bx, by = b ha = half(ax - ox, ay - oy) hb = half(bx - ox, by - oy) if ha != hb: return -1 if ha > hb else 1 c = ccw(ox, oy, ax, ay, bx, by) if c != 0: return -1 if c > 0 else 1 da = (ax - ox)**2 + (ay - oy)**2 db = (bx - ox)**2 + (by - oy)**2 return -1 if da < db else 1 if da > db else 0 return cmpn = int(input())P = [tuple(map(int, input().split())) for _ in range(n)]O = P[0]P.sort(key=cmp_to_key(angle_cmp(O)))for x, y in P: print(x, y)
// 각도 정렬 (CCW comparator)import java.util.*;import java.io.*;public class Main { static class Point { long x, y; Point(long x, long y) { this.x = x; this.y = y; } } static long ccw(Point a, Point b, Point c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } static boolean half(Point p) { return p.y > 0 || (p.y == 0 && p.x < 0); } static long dist2(Point a, Point b) { long dx = a.x - b.x, dy = a.y - b.y; return dx * dx + dy * dy; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); Point[] P = new Point[n]; for (int i = 0; i < n; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); P[i] = new Point(Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken())); } Point O = P[0]; Arrays.sort(P, (a, b) -> { boolean ha = half(new Point(a.x - O.x, a.y - O.y)); boolean hb = half(new Point(b.x - O.x, b.y - O.y)); if (ha != hb) return ha ? -1 : 1; long c = ccw(O, a, b); if (c != 0) return c > 0 ? -1 : 1; return Long.compare(dist2(O, a), dist2(O, b)); }); StringBuilder sb = new StringBuilder(); for (Point p : P) sb.append(p.x).append(' ').append(p.y).append('\n'); System.out.print(sb); }}
stdin
40 01 00 1-1 0
결과
0 00 1-1 01 0
복잡도
항목
값
정렬 시간
O(N log N)
CCW 비용
O(1) (정수 곱셈 2회)
공간
O(N)
변형 / 활용
Graham scan (Convex Hull): 최하단-최좌측 점 기준 각도 정렬 후 스택으로 CCW > 0 인 점만 유지.
단순 다각형 생성 (BOJ 3679): 각도 정렬로 항상 교차 없는 star-shaped 다각형.
시계 정렬: CCW 반환값 부호 반전.
중심 기준 정렬: CCW comparator 의 O 만 변경.
함정
strict weak ordering: ccw(O, a, b) > 0 만 반환하면 non-transitive. 사분면 분할 필수.
기준점과 동일 점: O 와 같은 점은 첫 번째로 분리.
Collinear: 각도가 같으면 거리순 정렬. 용도에 따라 가까운/먼 순 선택.
atan2 문제: [-pi, pi] 반환 → [0, 2pi) 변환 필요. double 비교가 strict weak ordering 깨뜨릴 수 있음.
💬 댓글