꼭짓점이 둥근 볼록껍질(round convex hull)의 둘레의 길이를 구하는 법

1. 문제

 

10903번: Wall construction (acmicpc.net)

10903번: Wall construction

 

2. 풀이

 

convex hull의 둘레의 길이를 구해야하는데.. 단순히 둘레의 길이만 구한다면.. convex hull의 모든 꼭짓점을 찾고

 

꼭짓점끼리 거리를 합하면 그만이지만 이 문제는 꼭짓점이 둥근 형태라는게 문제다.

 

 

convex hull의 꼭짓점을 찾고 꼭짓점끼리 거리를 구한다음, 파란색으로 동그라미 된 둥근 부분의 길이도 구해야한다

 

이를 위해서.. convex hull의 꼭짓점을 먼저 모두 찾고, 꼭짓점끼리 거리는 유클리드 거리로 일단 구해주고..

 

꼭짓점 3개 i,i+1,i+2번에 대해서.. 두 벡터 (i,i+1), (i+1,i+2)가 이루는 각도를 구해가지고

 

부채꼴의 호의 길이는 반지름 * 원주각으로 구할 수 있다는 것을 이용한다.

 

https://houseofj.tistory.com/152

부채꼴의 호의 길이와 부채꼴의 넓이 공식 및 증명하기

 

 

 

두 벡터가 이루는 각은 어떻게 구하냐?

 

$$cos \theta = \frac{a * b}{|a||b|}$$

 

위 식으로 cos값을 구하면, acos으로 각도 값을 구할 수 있다.

 

 

https://asteriskhun.tistory.com/40

[Vector] 두 벡터 사이의 각도 구하기 (내적/외적)

 

 

import math
from sys import stdin

def ccw(x,y):
    
    return x[0]*y[1] - x[1]*y[0]

#두 점 x,y사이 거리
def distance(x,y):
    
    return ((x[0]-y[0])**2 + (x[1]-y[1])**2)**(1/2)

#세 점 x,y,z를 받아 (x,y), (y,z)사이 각도를 구해 
#두 벡터가 이루는 부채꼴의 호의 길이 l = r*theta를 구한다
def cylinder(x,y,z,r):
    
    a = [y[0]-x[0],y[1]-x[1]]
    b = [z[0]-y[0],z[1]-y[1]]

    cos = (a[0]*b[0] + a[1]*b[1])/(distance(a,[0,0]) * distance(b,[0,0]))

    return r*math.acos(cos)

#monotone chain으로 convex hull을 구하는 알고리즘
def monotone(points,r):
    
    points.sort()

    upper = [0,1]
    lower = [0,1]

    for i in range(2,n):
        
        while len(upper) >= 2:
            
            x = [points[upper[-1]][0] - points[upper[-2]][0], points[upper[-1]][1] - points[upper[-2]][1]]
            y = [points[i][0] - points[upper[-2]][0], points[i][1] - points[upper[-2]][1]]

            v = ccw(x,y)

            if v < 0:
                
                upper.append(i)
                break
            
            else:
                
                upper.pop()
        
        if len(upper) <= 1:
            
            upper.append(i)
        
        while len(lower) >= 2:
            
            x = [points[lower[-1]][0] - points[lower[-2]][0], points[lower[-1]][1] - points[lower[-2]][1]]
            y = [points[i][0] - points[lower[-2]][0], points[i][1] - points[lower[-2]][1]]

            v = ccw(x,y)

            if v > 0:
                
                lower.append(i)
                break
            
            else:
                
                lower.pop()
        
        if len(lower) <= 1:
            
            lower.append(i)
    
    #upper의 0~len(upper)-1까지는 윗껍질
    #lower의 len(lower)-2부터 1까지는 아래 껍질이므로, 이를 윗껍질에 append하면 전체 convex hull
    for i in range(len(lower)-2,0,-1):
        
        upper.append(lower[i])
    
    answer = 0

    upper.append(upper[0])
    upper.append(upper[1])
    
    #두 꼭짓점 사이 직선 거리를 구하고
    for i in range(len(upper)-2):

        answer += distance(points[upper[i]], points[upper[i+1]])
    
    #꼭짓점의 부채꼴의 호의 길이를 구해준다.
    for i in range(len(upper)-2):

        answer += cylinder(points[upper[i]],points[upper[i+1]],points[upper[i+2]],r)

    return answer     
        
n,r = map(int,stdin.readline().split())

points = []

for _ in range(n):
    
    x,y = map(int,stdin.readline().split())

    points.append((x,y))

circum = monotone(points,r)

print(circum)

 

 

3. 다른 풀이

 

사실은 훨씬 간단한 풀이가 있는데 아래 그림을 자세히 관찰해보면...

 

 

convex hull은 사실 하나의 중심을 기준으로 1바퀴 도는것과 같다.

 

그러니까, 구해야하는 둘레의 길이 합은, 결국 원기둥의 전체 둘레의 길이와 같으므로,

 

꼭짓점끼리 직선거리 합에 $2 \pi r$을 더해주면 된다

 

import math
from sys import stdin

def ccw(x,y):
    
    return x[0]*y[1] - x[1]*y[0]

#두 점 사이 거리
def distance(x,y):
    
    return ((x[0]-y[0])**2 + (x[1]-y[1])**2)**(1/2)

#monotone chain으로 convex hull을 구하는 알고리즘
def monotone(points,r):
    
    points.sort()

    upper = [0,1]
    lower = [0,1]

    for i in range(2,n):
        
        while len(upper) >= 2:
            
            x = [points[upper[-1]][0] - points[upper[-2]][0], points[upper[-1]][1] - points[upper[-2]][1]]
            y = [points[i][0] - points[upper[-2]][0], points[i][1] - points[upper[-2]][1]]

            v = ccw(x,y)

            if v < 0:
                
                upper.append(i)
                break
            
            else:
                
                upper.pop()
        
        if len(upper) <= 1:
            
            upper.append(i)
        
        while len(lower) >= 2:
            
            x = [points[lower[-1]][0] - points[lower[-2]][0], points[lower[-1]][1] - points[lower[-2]][1]]
            y = [points[i][0] - points[lower[-2]][0], points[i][1] - points[lower[-2]][1]]

            v = ccw(x,y)

            if v > 0:
                
                lower.append(i)
                break
            
            else:
                
                lower.pop()
        
        if len(lower) <= 1:
            
            lower.append(i)
    
    #upper의 0~len(upper)-1까지는 윗껍질
    #lower의 len(lower)-2부터 1까지는 아래 껍질이므로, 이를 윗껍질에 append하면 전체 convex hull
    for i in range(len(lower)-2,0,-1):
        
        upper.append(lower[i])
    
    answer = 0

    upper.append(upper[0])
    upper.append(upper[1])
    
    #전체 convex hull의 둘레의 길이는.. 
    
    ##두 꼭짓점 사이 직선 거리를 구하고
    for i in range(len(upper)-2):

        answer += distance(points[upper[i]], points[upper[i+1]])
    
    #convex hull은 결국 하나의 중심을 기준으로 한바퀴 도는 것과 같으므로
    #모든 부채꼴의 호의 길이 합은, 결국 원기둥의 밑면의 둘레의 길이와 같으니까
    #꼭짓점끼리 직선거리 합에 반지름이 r인 원의 둘레의 길이를 합하면 된다
    answer += 2*math.pi*r

    return answer     
        
n,r = map(int,stdin.readline().split())

points = []

for _ in range(n):
    
    x,y = map(int,stdin.readline().split())

    points.append((x,y))

circum = monotone(points,r)

print(circum)