[백준/3679] 단순 다각형 (Python)

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

3679번: 단순 다각형

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 01:26:32

 

---

 

문제 설명

 

 

평면 위의 점의 집합이 주어졌을 때, 다각형을 만드는 프로그램을 작성하시오. 집합의 모든 점은 다각형의 꼭짓점이어야 하고, 집합에 없는 점을 다각형의 꼭짓점으로 가질 수 없다. 다각형의 두 선분은 연속하는 두 선분의 교점을 제외하고는 교차할 수 없다.

예를 들어, 왼쪽 그림의 점으로 만든 다각형은 오른쪽과 같다.

 

 

항상 문제의 조건을 만족하는 다각형만 입력으로 주어지며, 가능한 다각형이 여러 가지인 경우에는 아무거나 출력해도 된다. 두 점이 같은 위치에 있는 경우는 없으며, 모든 점이 한 직선위에 있는 경우는 없다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 테스트 케이스의 첫 번째 숫자는 점의 개수 n (3 ≤ n ≤ 2000) 이다. 다음 숫자는 점의 좌표 x와 y이며, 좌표는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

 

출력

 

각 테스트 케이스마다 0부터 n-1까지 순열중 하나를 출력해야 한다. 출력하는 순열은 입력으로 주어지는 점의 번호를 나타내며, 출력하는 순서대로 점을 이었을 때, 올바른 다각형을 만들어야 한다.

 

입력 예시

 

2
4 0 0 2 0 0 1 1 0
5 0 0 10 0 10 5 5 -1 0 5

 

출력 예시

 

0 3 1 2
3 1 2 4 0

 

 

---

 

풀이

 

 

볼록 다각형, Convex Hull을 사용할 때 우리는 각도 순으로 반시계 방향으로 정렬하는 것을 이용했는데, 이 반시계 방향으로의 정렬을 이용하면 된다.

 

정렬을 수행할 때

 

• 기준점과의 각도 순으로
• 각도가 같다면 기준점과의 거리 순으로 오름차순으로

 

정렬하면, 그 정렬 후 결과물은 볼록다각형이 된다. 기준점과 다른 각도의 두 점을 이은 직선들은 서로 교차하지 않고, 같은 각도상에 있다면 직선 위에 있는 셈이다. 주의할 점은, 마지막 점과 동일 직선에 있는 경우, 이 경우는 거리 순으로 내림차순으로 정렬되어야 한다는 점이다(마지막 점에 한해서 출발점으로 돌아와야 하기 때문이다)

 

 

풀이 코드

import sys
from functools import cmp_to_key
input = sys.stdin.readline

def ccw(a, b, c) :
  return (a[0]*b[1] + b[0]*c[1] + c[0]*a[1]) - (a[1]*b[0] + b[1]*c[0] + c[1]*a[0])

def dist(a, b) :
  return (a[0]-b[0])**2+(a[1]-b[1])**2

def cmp(a, b) :
  if ccw(ref, a, b) > 0 :
    return 1
  if ccw(ref, a, b) == 0 and dist(ref, a) > dist(ref, b) :
    return 1
  return -1

def solve() :
  global ref
  N, *raw = map(int, input().split())

  points = list()
  ref = (10001, 10001, -1)
  for i in range(N) :
    p = (raw[2*i], raw[2*i+1], i)
    points.append(p)
    if ref > p :
      ref = p
  points.sort(key = cmp_to_key(cmp))
  last, last_ref = list(), points[-1]

  ans = [ref[2]]
  for p in points :
    if p == ref :
      continue
    if ccw(ref, last_ref, p) == 0 :
      last.append(p[2])
    else :
      ans.append(p[2])
  last.reverse()
  print(*(ans+last))

for _ in range(int(input())) :
  solve()

풀이 완료!