[Python] 30912번 위잉위잉

https://www.acmicpc.net/problem/30912

---

 

24/05/11

 

 

각도 정렬을 "잘" 구현해야 되는 문제이다.

---

 

문제 접근 방식:

 

 

처음으로 접근했던 방식은 파이썬 math모듈의 atan2함수를 이용한 정렬이다.

 

파이썬 공식 도큐먼트에 나와있는 atan2함수의 설명은 다음과 같다.

math.atan2(y, x)
Return atan(y / x), in radians. The result is between -pi and pi. The vector in the plane from the origin to point (x, y) makes this angle with the positive X axis. The point of atan2() is that the signs of both inputs are known to it, so it can compute the correct quadrant for the angle. For example, atan(1) and atan2(1, 1) are both pi/4, but atan2(-1, -1) is -3*pi/4.

 

어떠한 점이 주어져 있으면, 이 점이 위치한 벡터의 각도를 라디안으로 내뱉는 함수이다.

 

따라서, 이 함수를 key로 받아서 정렬하면 반시계 방향으로 정렬된다.

 

하지만 이 문제에서는 이 방법을 적용하면 실수오차 때문에 정렬에 실패하게 된다.

 

다양한 방법이 존재하지만, 이후의 나의 접근 방법은 functools모듈의 cmp_to_key함수를 활용하여, 기울기를 비교하는 함수를 구현하여 접근했다.

 

먼저 180도에 대한 비교 함수를 구현했다.

 

참고한 사이트는 다음과 같다.

https://lem0nad3.tistory.com/130 

기하 알고리즘 - 기초

 

원점을 기준으로 하여 $[-\pi/2, \pi/2]$의 범위에 놓여있는 점들을 모두 정렬하는 함수를 다음과 같이 구현했다.

# 원점에 대한 각도 정렬(반시계방향)
'''
범위는 -pi/2~pi/2 (y축 위의 점도 포함)
from functools import cmp_to_key
'''
def cmp(p1, p2):  # 두 점을 입력 받는다.
    if p1[0] == 0 and p2[0] == 0: # 두 점 모두 y축 위에 있을 때
        if p1[1]*p2[1] > 0: # 두 점의 y좌표가 같은 부호일 경우
            if abs(p1[1]) < abs(p2[1]):
                return 1
            elif abs(p1[1]) == abs(p2[1]):
                return 0
            else:
                return -1
        else: # 두 점의 y좌표가 다른 부호일 경우
            if p1[1] < p2[1]:
                return 1
            else:
                return -1
    else:
        if p1[1]*p2[0] < p1[0]*p2[1]:
            return 1
        elif p1[1]*p2[0] == p1[0]*p2[1]:
            if p1[0]**2 + p1[1]**2 < p2[0]**2 + p2[1]**2:
                return 1
            else:
                return -1
        else:
            return -1

 

이 함수는 1사분면과 4사분면 위, 혹은 2사분면과 3사분면 위에만 점들이 놓여 있을 때 비교해주는 함수이다.

 

일반적으로 기울기가 작다면 기울기가 큰 쪽으로 정렬되도록 함수를 구현했다. 이때, 실수오차를 내지 않기 위해 분모를 양변에 곱함으로써 실수연산을 사용하지 않도록 구현했다.

 

또한, 기울기가 같다면 원점에서부터 떨어진 거리를 구해서, 거리가 큰 순으로 정렬되도록 함수를 구현했다.

 

점들이 y축에 놓여있는 경우, 기울기를 구할 수 없기 때문에 예외처리를 진행해주었고, 이때도 마찬가지로 거리가 큰 순으로 정렬되도록 함수를 구현했다.

 

이 180도 정렬 함수를 발전시켜, 360도 정렬 함수를 구현했다.

 

360도 정렬은 180도 정렬 함수를 2번 적용하는 꼴로 구현했다. 2, 3사분면에 있는 점이 1, 4사분면에 있는 점보다 더 순서가 작도록 구현했다.

 

두 점이 모두 2, 3사분면에 있거나 1, 4사분면에 있다면 180도 정렬 함수를 적용하도록 구현했다.

# 원점에 대한 각도 정렬(360도 버전)
def cmp(p1, p2):  # 두 점을 입력 받는다.
    if p1[0]*p2[0] < 0:  # 만약 두 점의 x좌표가 다르게 위치해있다면
        if p1[0] < p2[0]: return 1
        else: return -1
    elif p1[0]*p2[0] == 0: # 두 점중 한 점이 x좌표가 0이라면
        if p1[0] == p2[0]:  # 두 점이 모두 y축 위에 있다면
            if p1[1]*p2[1] < 0:
                if p1[1] < p2[1]: return 1
                else: return -1
            else:
                if abs(p1[1]) < abs(p2[1]): return 1
                elif abs(p1[1]) == abs(p2[1]): return 0
                else: return -1
        elif p1[0] == 0:
            if p1[1] > 0: return -1
            else:
                if p1[0] < p2[0]: return 1
                else: return -1
        else:
            if p2[1] > 0: return 1
            else:
                if p1[0] < p2[0]: return 1
                else: return -1
    else:
        if p1[1]*p2[0] < p1[0]*p2[1]: return 1
        elif p1[1]*p2[0] == p1[0]*p2[1]:
            if p1[0]**2 + p1[1]**2 < p2[0]**2 + p2[1]**2: return 1
            else: return -1
        else: return -1

 

마찬가지로, 어느 한 점이 y축에 있는 경우는 예외처리를 해주기 위해 조금 코드가 길어지게 되었다.

 

이 비교 함수를 활용하여 정렬을 해주었다.

 

이때, $(X_H, Y_H)$를 원점으로 삼아서 정렬을 해주었다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 30912번 위잉위잉
# 기하, 정렬
'''
접근 방법:
기울기 비교
'''
import sys
input = sys.stdin.readline
from functools import cmp_to_key

# 원점에 대한 각도 정렬(360도 버전)
def cmp(p1, p2):  # 두 점을 입력 받는다.
    p1, p2 = (p1[0]-pivot[0], p1[1]-pivot[1]), (p2[0]-pivot[0], p2[1]-pivot[1])
    if p1[0]*p2[0] < 0:  # 만약 두 점의 x좌표가 다르게 위치해있다면
        if p1[0] < p2[0]:
            return 1
        else:
            return -1
    elif p1[0]*p2[0] == 0: # 두 점중 한 점이 x좌표가 0이라면
        if p1[0] == p2[0]:  # 두 점이 모두 y축 위에 있다면
            if p1[1]*p2[1] < 0:
                if p1[1] < p2[1]:
                    return 1
                else:
                    return -1
            else:
                if abs(p1[1]) < abs(p2[1]):
                    return 1
                elif abs(p1[1]) == abs(p2[1]):
                    return 0
                else:
                    return -1
        elif p1[0] == 0:
            if p1[1] > 0:
                return -1
            else:
                if p1[0] < p2[0]:
                    return 1
                else:
                    return -1
        else:
            if p2[1] > 0:
                return 1
            else:
                if p1[0] < p2[0]:
                    return 1
                else:
                    return -1
    else:
        if p1[1]*p2[0] < p1[0]*p2[1]:
            return 1
        elif p1[1]*p2[0] == p1[0]*p2[1]:
            if p1[0]**2 + p1[1]**2 < p2[0]**2 + p2[1]**2:
                return 1
            else:
                return -1
        else:
            return -1
    
N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]
pivot = tuple(map(int, input().split()))
P.sort(key = cmp_to_key(cmp), reverse=True)
for tpl in P:
    print(*tpl)