[BOJ] 백준 1198 삼각형으로 자르기 python

 

 

 

말이 어렵게 쓰여있지만, 결국 해답은 뭐냐면 

 

다각형의 세 점을 이어서 만들 수 있는 삼각형 중 가장 넓이가 큰 것을 찾으시오 라는 문제가 되겠습니다.

 

여기서, 아이디어로서 사용되는 것은 신발끈 정리입니다.

 

https://ko.wikipedia.org/wiki/%EC%8B%A0%EB%B0%9C%EB%81%88_%EA%B3%B5%EC%8B%9D

신발끈 공식 - 위키백과, 우리 모두의 백과사전

 

좌표 평면에 점의 좌표가 주어져 있을 때 다각형의 넓이를 구할 수 있게 도와주는 공식이예요.

 

이를 활용해 아래와 같이 코드를 짤 수 있겠습니다.

def area의 부분이 넓이를 구하는 함수가 되겠습니다.

 

from itertools import combinations
import math
def area(a,b,c):
    x1,y1 = a[0],a[1]
    x2,y2 = b[0],b[1]
    x3,y3 = c[0],c[1]
    return int(math.fabs(x1*y2 + x2*y3 + x3*y1 - x2*y1 - x3*y2 - x1*y3)) * 1/2
ans = -1
N = int(input())
pts = []
for _ in range (0,N):
    pt = list(map(int,input().split()))
    pts.append(pt)

for t in combinations(pts,3):
    t = list(t)
    a,b,c = t[0],t[1],t[2]
    ans = max(ans, area(a,b,c))
print(ans)