[백준]_1064번 : 평행사변형(파이썬 and C언어)

1064번: 평행사변형

필자에게 이 문제는 백준 문제풀이 사상 최초로 아이디어가 하나도 안 떠올라 샷건을 치고 구글에 솔루션을 검색하여 예상보다 너무 간단했던 해결책에 절망했던 문제이다. 이 글을 찾아준 독자들 또한 같은 여정을 견디고 온 것이라 생각한다. 이제 이 문제를 구현하려면 어떤 사고과정이 수반되었어야 하는지 살펴나가 보자.

---

관찰

아마 가장 많이 떠올랐을 해결책은 어차피 세 점이 주어졌을 때 존재할 수 있는 평행사변형은 많아봐야 3개이기 때문에 "3개쯤이야 뭐 좌표 구하고 그다음에 둘레 구해서 최대 최소 찾으면 되지 뭐~" 이렇게 생각할 수 있다. 하지만 이런 접근 방식은 우리를 미궁으로 빠뜨린다. 왜냐하면 우리가 네 번째 점을 찾는 데 사용되는 능력을 컴퓨터로 구현하려면 매우 복잡해지기 때문이다. 

 

여기서 말하는 인간의 능력이란... 우리가 네 번째 점을 찾기 위해서 어떻게 하는가 생각해보면 된다. 임의의 점 2개를 1쌍씩 짝지어 선분을 그린 후 그 선분들을 평행시키고 교점을 찾으면 그것이 네 번째 점 아닌가!! 하지만 선분 그리기, 평행이동 시키기, 교점 찾기를 컴퓨터에게 어떻게 설명해 줄 것인가?!?

 

그래서 다른 관점으로 문제를 접근해볼 필요가 있음을 알 수 있다.

---

Desmos

Desmos를 이용해 우리가 처한 상황을 시각화 해보자. 점 A, B, C가 문제에서 주어진 세 점이라고 가정하고 후보1, 후보2, 후보3은 평행사변형을 완성시킬 수 있는 점들이라고 할 수 있다. 

 

어느 점을 선택해야지 둘레의 길이가 최대 또는 최소인지 알 수 있을까?

 

그것은 바로 평행사변형 둘레가 어떻게 계산되는지 눈치 채면 알 수 있다!! A, B, C로 만들 수 있는 변 2개의 길이의 합 * 2 가 결국 둘레다!!

(후보1~3 어디든지 잡고 계산해 보아라)

 

따라서 구할 수 있는 평행사변형 둘레의 최댓값은 2(ac+bc)-2(ab+bc)=2(최대 선분 길이 - 최소 선분 길이) 이다.

 

시도 1(Python)

import math
def distance(a,b):
    return math.sqrt((a**2)+(b**2))
def tan(a,b,c,d,e,f):
    if (a-c)*(d-f)==(c-e)*(b-d):
        return True
    else:
        return
x1,y1,x2,y2,x3,y3=map(int, input().split())
if tan(x1,y1,x2,y2,x3,y3):
    print('-1')
else:
    ab=distance((x1-x2),(y1-y2))
    bc=distance((x2-x3),(y2-y3))
    ca=distance((x1-x3),(y1-y3))
    lenght=[ab,bc,ca]
    result=max(lenght)-min(lenght)
    print(result*2)

<해석>

먼저 평행사변형을 만들 수 있는 환경인지 아닌지 알아보기 위해 tan() 함수에 세 점의 좌표들을 전달해 세 점이 한 직선 위에 있는지 검사한다. 그다음 distance() 함수에 점 2개의 좌표를 차례대로 넣어 선분의 길이를 구해주고 최댓값에서 최솟값을 뺀 값에 2배를 한 결과를 출력한다.

 

시도 2(C언어)

#include <stdio.h>
#include <math.h>
int tan(int a, int b, int c, int d, int e, int f){
    if((a-c)*(d-f)==(c-e)*(b-d)) return 1;
    else return 0;
}
double max(double a, double b, double c){
    double long_side=(a>b) ? a:b;
    long_side=(long_side>c) ? long_side:c;
    return long_side;
}
double min(double a, double b, double c){
    double short_side=(a<b) ? a:b;
    short_side=(short_side<c) ? short_side:c;
    return short_side;
}
int main() {
    int x1,x2,x3,y1,y2,y3;
    scanf("%d %d %d %d %d %d", &x1,&y1,&x2,&y2,&x3,&y3);
    if(tan(x1,y1,x2,y2,x3,y3)) printf("-1");
    else{
        double ab,bc,ca;
        ab=sqrt(pow(x1-x2,2)+pow(y1-y2,2));
        bc=sqrt(pow(x3-x2,2)+pow(y3-y2,2));
        ca=sqrt(pow(x1-x3,2)+pow(y1-y3,2));
        printf("%.15f",2*(max(ab,bc,ca)-min(ab,bc,ca)));	
    }
}

<해석>

위의 파이썬 코드와 전체적인 개요는 똑같지만 코드가 너무 길어지는 것을 방지하기 위해 distance()  함수를 삭제했고 선분의 최대 최소를 구하는 데에 삼항연산자를 사용하였다.