[BOJ 3679] 단순 다각형

문제

---

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

풀이

---

이런 문제는 대게 기준점을 잡고, 각 점을 기준점과 이은 선분과 x축이 이루는 각도를 기준으로 정렬을 한다.

각도가 같을 시엔 x 좌표, y 좌표 등으로 우선순위를 추가로 매긴다.

이 문제의 경우엔 y 좌표가 제일 작은 것을 기준점으로 잡는다.

그런 것이 여러 개 있다면 x 좌표가 제일 작은 것을 기준점으로 잡는다.

그 후 각도가 증가하는 순서로 점들을 골라주면 된다.

만약 첫 단계에서 여러 점들이 일직선상에 놓여있으면 기준점에서 멀어지는 순서대로 골라주면 된다.

마지막 단계에서 여러 점들이 일직선상에 놓여있으면 기준점에 가까워지는 순서대로 골라주면 된다.

코드

---

import sys


def tangent(x, y):
    if x > a:
        return 0, (y - b) / (x - a), -x
    if x == a:
        return 1, -y
    if x < a:
        return 2, (y - b) / (x - a), x


for _ in range(int(sys.stdin.readline())):
    data = list(map(int, sys.stdin.readline().split()))
    
    coord = [(data[2 * i + 1], data[2 * i + 2], i) for i in range(data[0])]
    coord.sort(key=lambda x: (x[1], x[0]))
    a, b, j = coord.pop(0)
    coord.sort(key=lambda x: tangent(x[0], x[1]))

    if coord[0][0] == a:
        slope_start = float('inf')
    else:
        slope_start = (b - coord[0][1]) / (a - coord[0][0])
    
    idx = 0
    while True:
        idx += 1
        
        if coord[idx][0] == a:
            slope = float('inf')
        
        else:
            slope = (b - coord[idx][1]) / (a - coord[idx][0])
        
        if slope_start != slope:
            break

    res = [coord[i][2] for i in range(data[0] - 1)]
    print(j, *res[:idx][::-1], *res[idx:])