[알고리즘] 백준 1064 파이썬 - 평행사변형

 

1064번: 평행사변형

문제

평행사변형은 평행한 두 변을 가진 사각형이다. 세 개의 서로 다른 점이 주어진다. A(xA,yA), B(xB,yB), C(xC,yC)

이때, 적절히 점 D를 찾아서 네 점으로 평행사변형을 만들면 된다. 이때, D가 여러 개 나올 수도 있다.

만들어진 모든 사각형 중 가장 큰 둘레 길이와 가장 작은 둘레 길이의 차이를 출력하는 프로그램을 작성하시오. 만약 만들 수 있는 평행사변형이 없다면 -1을 출력한다.

 

문제풀이

x1,y1,x2,y2,x3,y3=map(int,input().split())

#01
if ((x1-x2)*(y1-y3) == (x1-x3)*(y1-y2)): # ((y1-y2)/(x1-x2) == (y1-y3)/(x1-x3))
    print(-1.0)
    quit()
#02
ab = ((x1-x2)**2+(y1-y2)**2)**0.5
bc = ((x1-x3)**2+(y1-y3)**2)**0.5
ca = ((x2-x3)**2+(y2-y3)**2)**0.5

#03
tmp = [ab+bc,ab+ca,bc+ca]
res = max(tmp)-min(tmp)
print(res*2)

- #01 : 3개의 점이 1개의 선분 위에 있으면 4개의 점으로 사각형을 생성할 수 없다.

           즉 그렇기에 3개의 점으로 기울기를 구하여서 기울기가 같은지 확인해본다.

           기울기가 같다면 -1.0을 출력하고 코드를 종료한다.

- #02 : 3개의 점으로 구할 수 있는 선분인 ab, bc, ca의 길이를 각각 구한다.

           평행사변형의 둘레는 2개의 선분으로 구할 수 있는 것을 이용하여 문제를 푼다.

- #03 : tmp에 2개의 선분을 더한 값을, 총 3개 저장한다.

           2개의 선분을 더한 값 중에서 가장 큰 값과 작은 값의 차를 구한다.

           이후 그 값에 2를 곱해주면 평행사변형 둘레의 차이가 나온다.

          

          가장 큰 둘레 =  (가장 긴 선분 + 중간 선분)*2 

          가장 작은 둘레 = (가장 작은 선분 + 중간 선분)*2

          둘의 차이 = (가장 긴 선분 - 가장 작은 선분)*2