[백준] 1064번 평행사변형, 파이썬 문제 풀이

문제

백준의 1064번 평행사변형의 둘레를 구하는 문제를 해결했습니다.

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

1064번: 평행사변형

문제

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

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

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

입력

첫째 줄에 xA yA xB yB xC yC가 주어진다. 모두 절댓값이 5000보다 작거나 같은 정수이다.

예시 : 0 0 0 1 1 0

출력

첫째 줄에 문제의 정답을 출력한다. 절대/상대 오차는 10-9까지 허용한다.

예시 : 0.8284271247461898

 

풀이 과정

사실, 문제를 처음 읽고 점 D를 구하기 위한 무수한 노력을 했습니다. 평행사변형을 만들기 위한 조건은 다음과 같습니다.

• 두 쌍의 대변은 길이가 각각 같다.
• 두 쌍의 대각은 각각 같다.
• 두 대각선은 서로 다른 대각선을 이등분한다.

기울기와 길이가 같은 점을 찾아야 하기 때문에, 길이로 접근해보고, 기울기로 접근해봤습니다. 아무리 생각해도 효율적인 방법이 떠오르지 않았습니다. 점 D가 될 수 있는 좌표를 아무리 줄여보려고 노력해도 최소 길이의 같은 기울기를 가진 좌표인데, 이를 프로그램으로 구현하는 것이 힘들었습니다.

 

계속해서 고민하다 보니, 점 D를 알 필요가 없다는 생각이 들었습니다. 문제는 점 D의 좌표를 구하는 것이 아닌, 평행사변형의 최대 둘레와 최소 둘레의 차를 구하는 것이기 때문입니다. 이미, 점 3개가 나왔기 때문에 선분이 최소 3개가 주어져있습니다. 2개는 같고, 다른 한 개가 다르기 때문에, 길이가 다른 선분 두개를 이용하면 둘레를 구할 수 있습니다.  

 

마지막으로 고민해야하는 것은, 평행 사변형을 만들지 못하는 경우를 찾는 것입니다. 세 개의 점이 한 개의 선분 위에 있으면 사각형을 만들 수 없습니다. 이는, 점 3개가 이루는 선분의 기울기가 같은 것을 의미합니다. 이 경우에, 각 3개의 기울기를 모두 비교할 필요없이 한 개의 기준점을 갖고 다른 두 개의 점과의 기울기를 비교하면 같은 기울기를 갖고 있는지 확인할 수 있습니다.

기울기는, Y변화량/X변화량으로 구할 수 있습니다. 이렇게 나눗셈 연산은 런타임 에러를 발생시킬 수 있기 때문에, 등식을 이항하여 조건식으로 활용했습니다.

 

코드

위 내용을 코드로 옮기면 다음과 같습니다.

ax, ay, bx, by, cx, cy = map(int, input().split())

if ((ax-bx)*(ay-cy)==(ay-by)*(ax-cx)):
    print(-1.0)
    exit(0)

ab_length = ((ax-bx)**2 + (ay-by)**2)**0.5
ac_length = ((ax-cx)**2 + (ay-cy)**2)**0.5
bc_length = ((bx-cx)**2 + (by-cy)**2)**0.5

length = [ab_length+ac_length, ab_length+bc_length, ac_length+bc_length]
result = max(length) - min(length)
print(2*result)

두 변을 더해서 2를 곱해야 하는데, 마지막에 한 번만 곱해줘도 될 것 같아서 마지막으로 미뤘습니다.

 

정리

전에, 다른 문제를 풀면서 열린 사고를 갖고 문제 풀이에 임하겠다고 생각한 적이 있는데, 이번에도 같은 생각을 했습니다. 한 번 경험이 있음에도 불구하고 처음에 생각한 풀이에서 벗어나는데 오래 걸렸다는 점은 스스로 실망스러운 모습이었습니다. 더 많은 문제를 풀면서 경험을 쌓아 능숙한 실력을 갖는 것이 목표입니다.