[백준 1198번] 파이썬 - 삼각형으로 자르기

https://www.acmicpc.net/problem/1198

1198번: 삼각형으로 자르기

 

 

 

# 조건

• 볼록 다각형이 있고 3개의 연속된 점을 선택해서 삼각형
• 만든 삼각형을 다각형에서 제외
• 원래 다각형이 N개의 점이 있엇다면, 이제 N-1개의 점으로 구성된 볼록 다각형이 된다.
• 위의 과정을 남은 다각형이 삼각형이 될 때까지 반복
• 점이 시계 방향순으로 주어지며, 마지막에 남은 삼각형은 여러 가지가 있을 수 있을 때, 넓이가 최댓값일 경우를 구하여라.

 

# 접근 방법

• 3개의 점을 선택해서 만들 수 있는 모든 삼각형의 넓이를 조사해준다.

 

# 삼각형 넓이 공식

• 세 변의 길이를 알 때
  • s = (a+b+c)/2
  • A = root(s(s-a)(s-b)(s-c))
• 세 좌표를 알 때
  • 하나의 좌표를 선택해서 나머지 두 좌표에서 빼준다.
  • S = 0.5 abs((b_x c_y - by c_x))
  • 또는
  • 0.5 abs(ax by + bx cy + cx ay - ay bx - by cx - cy * ax)

 

 

 

# 조건문을 반복문 안에서 안 돌려줘서 틀린 코드

N = int(input())
coordi = [list(map(int, input().split())) for _ in range(N)]


result = 0
# 좌표를 순회하며 삼각형 넓이 구해주기
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            # 각 변의 길이 구해주기
            a = ((coordi[i][0] - coordi[j][0])**2 + (coordi[i][1] - coordi[j][1])**2)**0.5
            b = ((coordi[i][0] - coordi[k][0])**2 + (coordi[i][1] - coordi[k][1])**2)**0.5
            c = ((coordi[k][0] - coordi[j][0])**2 + (coordi[k][1] - coordi[j][1])**2)**0.5
            # 헤론의 공식
            # A = (s(s-a)(s-b)(s-c))**0.5, s = (a+b+c)/2
            s = (a+b+c)/2
            A = (s*(s-a)*(s-b)*(s-c))**0.5
        if A > result:
            result = A

print(result)

 

# max 함수 이용 통과 코드

• 세 좌표를 가지고 구하기 version 1,2
• 헤론의 공식

# ==================================================================
# 세 좌표 가지고 구하기
N = int(input())
coordi = [list(map(int, input().split())) for _ in range(N)]


result = 0

for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            # ax = coordi[j][0] - coordi[i][0]
            # ay = coordi[j][1] - coordi[i][1]
            # bx = coordi[k][0] - coordi[i][0]
            # by = coordi[k][1] - coordi[i][1]
            #
            # result = max(0.5*abs(bx*ay-by*ax), rsult)
            result = max(0.5*abs(coordi[i][0]*coordi[j][1]+coordi[j][0]*coordi[k][1]+coordi[k][0]*coordi[i][1]-(coordi[i][1]*coordi[j][0]+coordi[j][1]*coordi[k][0]+coordi[k][1]*coordi[i][0])), result)


print(result)

# ========================================================================
# 헤론의 공식

N = int(input())
coordi = [list(map(int, input().split())) for _ in range(N)]

result = 0

# 좌표를 순회하며 삼각형 넓이 구해주기
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            # 각 변의 길이 구해주기
            a = ((coordi[i][0] - coordi[j][0])**2 + (coordi[i][1] - coordi[j][1])**2)**0.5
            b = ((coordi[i][0] - coordi[k][0])**2 + (coordi[i][1] - coordi[k][1])**2)**0.5
            c = ((coordi[k][0] - coordi[j][0])**2 + (coordi[k][1] - coordi[j][1])**2)**0.5
            # 헤론의 공식
            # A = (s(s-a)(s-b)(s-c))**0.5, s = (a+b+c)/2
            s = (a+b+c)/2
            result = max((s*(s-a)*(s-b)*(s-c))**0.5, result)
    
print(result)