글 읽기 - 4225 풀이과정이 이상한걸까요 아님 소수점 처리가 이상한걸까요?

nayounsang1 1년 전 0

제 생각은 후자인데..

예제 입출력

3
0 0
3 0
0 4
Case 1: 2.40
4
0 10
10 0
20 10
10 20
Case 2: 14.15
0

from math import atan2  # atan2(dy,dx)
from math import sqrt
from math import ceil


def ccw(p1, p2, p3):
    x1, y1 = p1
    x2, y2 = p2
    x3, y3 = p3
    return True if (x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3) > 0 else False


def dist(p1, p2, p3):  # p1,p2직선과 p3의 거리
    x1, y1 = p1
    x2, y2 = p2
    x3, y3 = p3
    # 직선 구하기
    # y - y1 = (x-x1)*(y2-y1)/(x2-x1)
    # (x2-x1)y + (y1-y2)x + y1(x1-x2) + x1(y2-y1) = 0
    a = y2 - y1
    b = x2 - x1
    c = y1 * b - x1 * a
    return abs(a * x3 + b * y3 + c) / sqrt(a ** 2 + b ** 2)


test = 1
while True:
    N = int(input())
    if N == 0:
        break
    points = []
    for _ in range(N):
        points.append(tuple(map(int, input().split())))
    # 데이터 전처리
    points.sort()
    points.sort(key=lambda x: x[1])  # y 제일 작은 것 중 x가 제일 작은 것
    start_p = points.pop(0)
    points.sort(key=lambda p: atan2(p[1] - start_p[1], p[0] - start_p[0]))  # 시작점과 각도가 작은순대로
    points = [start_p] + points
    # 볼록다각형화
    ch = [points[0], points[1]]
    for i in range(2, N):
        p = points[i]
        while len(ch) >= 2 and not ccw(ch[-2], ch[-1], p):
            ch.pop()
        ch.append(p)
    ######
    #ch:볼록다격형의 좌표
    min_val = float('inf')
    for i in range(len(ch) - 1):
        # i와 i+1 직선과 다른 점들의 점과 직선사이의 거리중 최대를 찾음
        p1, p2 = ch[i], ch[i + 1]
        max_val = 0
        for j in range(i): #0~i점까지
            val = dist(p1, p2, ch[j])
            max_val = max(max_val, val)
        for j in range(i + 2, len(ch)): #i+2~마지막 점까지
            val = dist(p1, p2, ch[j])
            max_val = max(max_val, val)
        min_val = min(max_val, min_val)#위에서 구한 점과 직선사이의 거리 중 최소값
    min_val = ceil(min_val*100)/100 
    print('Case {}: {:.2f}'.format(test, min_val))
    test += 1

nayounsang1 1년 전 0

오랜만에 보니 직선의방정식이 이상한거였네요~

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

4225 풀이과정이 이상한걸까요 아님 소수점 처리가 이상한걸까요?

nayounsang1 1년 전 0

nayounsang1 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말