백준 1064번 평행사변형

문제

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

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

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

문제풀이

사용한 알고리즘 : 구현

(1) 코드 19~23

 세 점이 한 직선 위에 있으면 평행사변형을 만들 수 없습니다.

(2) 코드 29~36

 세 점이 만드는 세 직선 중 2개를 뽑아 만들 수 있는 평행사변형의 둘레 길이 중 최대 - 최소 가 답입니다.

	#include <bits/stdc++.h>
	using namespace std;
	double a1, b1, a2, b2, a3, b3;
	double Dist(double A1, double B1, double A2, double B2){
	return sqrt((A1-A2)*(A1-A2)+(B1-B2)*(B1-B2));
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> a1 >> b1 >> a2 >> b2 >> a3 >> b3;
	double M1 = 1987654321;
	double M2 = 1987654321;
	if(a1!=a2) M1 = abs(b2-b1)/abs(a2-a1);
	if(a2!=a3) M2 = abs(b3-b2)/abs(a3-a2);
	// 점 3개가 한 직선에 있는 경우 (기울기가 같은경우)
	if(M1==M2){
	cout << -1 << '\n';
	return 0;
	}
	// 3개의 변
	double A = Dist(a1,b1,a2,b2);
	double B = Dist(a1,b1,a3,b3);
	double C = Dist(a2,b2,a3,b3);
	// 3개 변 중 2개 골라서 평행 사변형 만들었을 때 둘레 길이
	double len1 = 2*(A+B);
	double len2 = 2*(B+C);
	double len3 = 2*(C+A);
	cout<<fixed;
	cout.precision(16);
	cout << max(len1,max(len2,len3)) - min(len1,min(len2,len3)) << '\n';
	return 0;
	}

view raw BOJ 1064.cpp hosted with ❤ by GitHub