Wall construction(BOJ 10903)

태완·2023년 1월 18일
0

algorithm

목록 보기
6/7

기둥의 둘레만큼 각 벽을 평행이동 한다고 생각해보자.

만약 4면의 길이가 각각 1일때 기둥이 없다면 둘레는 4가 될 것이다.

각 모퉁이에 반지름 2짜리 기둥을 세운다고 생각하면, 각 모퉁이는 원을 1/4로 자른 모양의 둥근 모퉁이가 될 것이다. 그 크기는 2pi(반지름2)*1/4이 될 것이다.

그렇게 되면 각 모퉁이에 기둥을 세웠다고 해도, 각 벽은 평행이동 한 상태로 그림이 그려질 것이다

따라서 점들의 둘레의 길이 + 2pi(반지름)을 구하면 된다.

import sys
from collections import deque
import math
input = sys.stdin.readline

def ccw(p1, p2, p3):
    return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])

def convex_hull(points):
    points = sorted(points)
    lower = [] # 왼쪽에서 오른쪽으로
    for p in points:
        while len(lower) >= 2 and ccw(lower[-2], lower[-1], p) <= 0: # <= 0 이면 같은 직선에 있는 점도 포함
            lower.pop()
        lower.append(p)
    upper = [] # 오른쪽에서 왼쪽으로
    for p in reversed(points):
        while len(upper) >= 2 and ccw(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1] # 시작점과 끝점이 중복되므로 제거

def getDist(p1,p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

N, L = map(int, input().split())
points = [list(map(int, input().split())) for _ in range(N)]
c = convex_hull(points) # 볼록껍질을 이루는 점들
total = 0
for i in range(len(c)):
    total += getDist(c[i-1], c[i]) # 볼록 껍질을 이루는 점들의 길이를 다 더함
total += math.pi*L*2 # 만약 N이 4면, 4면을 더하고 1/4씩 각 모퉁이를 더하는거랑 같음
print(f"{total:.12f}")
profile
학생입니다.

1개의 댓글

comment-user-thumbnail
2023년 7월 2일

Prima Ready Mix adalah supplier cor beton jayamix yang sangat berpengalaman pada pekerjaan pengecoran. Sehingga, https://primareadymix.com/harga-cor-beton-jayamix-per-kubik/ yang kami tawarkan sangat bisa diandalkan.
Produk Lainnya :
1. https://primareadymix.com/harga-ready-mix-beton/
2. https://primareadymix.com/harga-jasa-trowel-floor-hardener-lantai-beton/
3. https://primareadymix.com/jayamix-terdekat-ready-mix-cor-beton/

Kwalitas yang teratas merupakan perantara kami menyediakan service yang tidak salah sesuai sama Beton Cor Ready Mix Per M3 yang Anda harapkan. Sehingga, ayo kita lihat https://primamixer.com/harga-ready-mix-per-m3/.
Produk Terpopuler :
1. https://primamixer.com/harga-daun-panel-beton-precast/
2. https://primamixer.com/harga-tiang-kolom-panel-beton-precast/
3. https://primamixer.com/harga-pagar-panel-beton-precast/

Kami Prima Precast mempersembahkan produk https://primaprecast.com/harga-u-ditch-beton-saluran-air-jual-cover-penutup/ dengan segudang pilihan sebentuk. Maka begitu, harga pracetak yang murah juga bernilai teratas menjadikan pembangunan Anda merupakan tidak sukar.
Produk Terbaru :
1. https://primaprecast.com/harga-tutup-u-ditch/
2. https://primaprecast.com/harga-beton-u-ditch-depok/
3. https://primaprecast.com/beton-u-ditch-bandung/

답글 달기