격자점 컨벡스 헐
난이도
Platinum 5
인증
문제
정수좌표를 갖는 점을 격자점이라고 한다. 격자 다각형은 모든 꼭짓점이 격자점으로 이루어진 다각형이다.
만약, 다각형의 두 꼭짓점을 잇는 모든 선분이 다각형 내부(또는 경계)에 있다면, 이 다각형을 볼록 다각형이라고 한다. 즉, 다각형의 내부각이 모두 180도 보다 작은 것이다.
격자점으로 이루어진 집합 S가 주어졌을 때, S의 모든 격자점을 포함하는 가장 작은 볼록 (격자) 다각형을 컨벡스 헐이라고 한다. 컨벡스 헐의 꼭짓점은 모두 S에 포함된 격자점이어야 한다. 만약, 모든 점이 같은 일직선 상에 있다면, 컨벡스 헐은 선분이 될 것이다. (오른쪽 그림)
아래 그림에서 집합에 포함된 점은 굵은 점으로, 컨벡스 헐의 꼭짓점은 X로, 변은 선분으로 나타낸 그림이다.
격자 다각형의 꼭짓점의 일반적인 순서는 다음과 같다.
첫 번째 꼭짓점은 y좌표가 가장 큰 점이다. 만약, 그러한 점이 2개라면, x가 작은 점이 첫 번째 점이다. 그 다음 점부터는 시계방향 순서이다. 격자점의 집합이 주어졌을 때, 컨벡스 헐을 일반적인 순서로 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 P(1 ≤ P ≤ 1000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 집합에 포함된 격자점의 수 N(3 ≤ N ≤ 50)이 주어진다. 나머지 줄은 집합에 포함되어 있는 격자점의 좌표가 한 줄에 5개씩 주어진다. (마지막 줄은 이보다 적을 수 있다) 모든 점은 x와 y좌표가 순서대로 주어지며, 공백으로 구분되어 있다. 좌표는 절댓값이 20보다 작거나 같은 정수이다.
출력
각 테스트 케이스에 대해서, 첫째 줄에는 컨벡스 헐에 포함된 점의 수를 출력한다. 그 다음 줄부터 컨벡스헐에 포함된 격자점을 한 줄에 하나씩 일반적인 순서대로 출한다. x와 y를 공백으로 구분하여 출력한다.
예제 입력
4
25
2 1 7 1 1 2 9 2 1 3
10 3 1 4 10 4 1 5 10 5
2 6 10 6 2 7 9 7 3 8
8 8 4 9 7 9 6 2 3 3
5 4 7 5 8 6 4 6 3 7
30
3 9 6 9 3 8 9 8 3 7
12 7 2 6 12 6 2 5 12 5
2 4 12 4 1 3 11 3 1 2
11 2 1 1 11 1 1 0 10 0
4 -1 10 -1 7 -2 10 -2 5 0
7 3 4 5 6 8 3 1 2 6
3
3 1 2 2 1 3
6
1 3 19 1 4 2 2 1 11 2
10 1
예제 출력
10
4 9
7 9
10 6
10 3
9 2
7 1
2 1
1 2
1 5
2 7
8
3 9
6 9
12 7
12 4
10 -2
7 -2
1 0
1 3
2
1 3
3 1
4
1 3
11 2
19 1
2 1
해설 및 후기
이 문제는 나에겐 볼록 껍질보다 더 어려웠다. 왜냐하면 문제 자체가 그레이엄 스캔을 의도하고 있기 때문이다. 그러나 외부 라이브러리를 import해서 정렬하는 방식을 웬만하면 쓰고싶지 않아서 지금 가지고 있는 방법중에 해결할 수 있는 방법을 찾다가, 이전 모노톤 알고리즘에서 순서만 살짝 변형시켜 출력하는 쪽으로 구현했다.
제출 코드
import sys
n = int(sys.stdin.readline().rstrip())
def ccw(a,b,c):
res = (b[0]-a[0])*(c[1]-a[1]) - (c[0]-a[0])*(b[1]-a[1])
if(res < 0):
return -1
elif(res > 0):
return 1
else:
return 0
for i in range(n):
lsts = []
m = int(sys.stdin.readline().rstrip())
maxX = -1
maxY = -1
cnt = 0
if(m%5 != 0):
cnt+=1
cnt += m//5
for j in range(cnt):
type = 0
x = 0
for k in sys.stdin.readline().rstrip().split():
if(type == 0):
x = int(k)
type = 1
else:
lsts.append([x,int(k)])
if(maxY == -1):
maxX = x
maxY = int(k)
else:
if(maxY < int(k)):
maxX = x
maxY = int(k)
elif(maxY == int(k)):
if(maxX > x):
maxX = x
type = 0
lsts = sorted(lsts, key=lambda x:(x[0], x[1]))
resCnt = 0
stk = []
for point in lsts:
while(len(stk)>1 and ccw(stk[-2], stk[-1], point)<=0):
stk.pop()
stk.append(point)
resCnt += len(stk)
tmpStk = stk[:]
stk = []
for point in lsts:
while(len(stk)>1 and ccw(stk[-2], stk[-1], point)>=0):
stk.pop()
stk.append(point)
resCnt += len(stk)
print(resCnt-2)
chk = False
for tx,ty in stk:
if(tx == maxX and ty == maxY):
chk = True
if(chk):
print(tx,ty)
for tx,ty in list(reversed(tmpStk))[1:-1]:
print(tx,ty)
for tx,ty in stk:
if(tx == maxX and ty == maxY):
break
print(tx,ty)