문제

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

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

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

입력

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

출력

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

예제 입력

0 0 0 1 1 0

예제 출력

0.8284271247461898

내가 했던 풀이 방법

평행사변형이 될 수 없는 경우부터 찾아주어야 한다. 평행사변형이 될 수 없는 경우는 A, B, C 중에 같은 위치에 있는 점이 있을 경우 또는 A, B, C가 일직선상에 위치한 경우이다.
A, B, C 중 같은 위치에 있는 점이 있는 경우는 ===을 이용해 쉽게 찾을 수 있다.
A, B, C가 일직선상에 위치할 수 있는 경우는 벡터의 외적을 이용해 구할 수 있다. 외적이 0이라는 것은 두 벡터가 같은 방향(또는 반대 방향)을 가리키고 있다는 것을 의미하기 때문에 벡터의 외적이 0일 때를 찾아주면 된다.벡터의 외적은 다음과 같이 계산할 수 있다.
[알고리즘/Python] CCW 알고리즘 : 벡터의 외적 해당 게시글에 자세하게 설명되어 있다.
즉, CCW 공식 (Bx-Ax) * (Cy-Ay) - (Cx-Ax) * (By-Ay)이 0일 때 일직선상에 위치해 평행사변형을 만들 수가 없다.

이렇게 평행사변형이 만들어질 수 없는 경우를 모두 찾았다면, A, B, C끼리의 거리를 구하고 가장 긴 길이와 가장 짧은 길이를 구해주면 된다. 점 D를 굳이 구하지 않는 이유는 평행사변형은 두 쌍의 대변의 길이가 같아야 하기 때문에 구하지 점D를 찾아서 길이를 구하지 않아도 이미 알 수 있다. 쉽게 말하면 AB > AC > BC 순으로 길이가 길 때 최대 둘레는 2*AB+2*AC일테고 최소 둘레는 2*BC+2*AC이다. 여기서 2*AC는 중복되므로 신경쓰지 않아도 될 것이다. 즉, 점 D을 알지 못해도 둘레는 알 수 있다는 것이다.

따라서 평행사변형이 만들어질 수 있는 경우라면 두 점 사이의 거리를 이용해서 AB, AC, BC의 길이를 찾아주고 이 중 가장 큰 길이와 가장 작은 길이를 각각 2배해준 값을 뺀 값이 둘레의 차이가 될 것이다.

코드

const fs = require('fs');
const input = fs.readFileSync(0, 'utf-8').toString().trim().split(' ').map(Number);

let [Ax, Ay, Bx, By, Cx, Cy] = input;

if ((Ax === Bx && Ay === By) || (Ax === Cx && Ay === Cy) || (Bx === Cx && By === Cy)) {
  console.log(-1);
} else if ((Bx - Ax) * (Cy - Ay) === (By - Ay) * (Cx - Ax)) {
  console.log(-1);
} else {
  let AB = Math.sqrt((Bx - Ax) ** 2 + (By - Ay) ** 2);
  let AC = Math.sqrt((Cx - Ax) ** 2 + (Cy - Ay) ** 2);
  let BC = Math.sqrt((Cx - Bx) ** 2 + (Cy - By) ** 2);

  let maxLength = Math.max(AB, AC, BC);
  let minLength = Math.min(AB, AC, BC);

  console.log(2 * maxLength - 2 * minLength);
}

회고

평행사변형이 일직선상에 있어야 하는 조건을 몰라서 조금 돌아갔던 문제. CCW 알고리즘이라는 걸 또 알게됐으니 기억해두고 유용하게 써먹어야겠다.