[C++]백준 - 1064번 문제

1064번: 평행사변형 (acmicpc.net)

1064번: 평행사변형

 

1064번 : 평행사변형

---

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

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

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

 

입력

---

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

 

 

출력

---

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

 

 

 

---

 

생각해 볼 점

---

세 점이 주어졌을 때, 나머지 한점으로 평행사변형을 만들 수 없는 경우는

 

세 점이 모두 평행한 선에 있을 때 빼고는 없습니다.

 

따라서, 우선 세 점이 평행한 선에 존재하는지 확인합니다.

 

 

CCW 알고리즘을 이용하여 확인합니다.

 

[알고리즘] CCW로 세 점의 방향성 판별하기 (tistory.com)

[알고리즘] CCW로 세 점의 방향성 판별하기

 

만약 평행 사변형을 만들 수 있는 경우에는,

 

총 세가지 평행 사변형을 만들 수 있습니다.

 

1. AB, BC 변을 이용한 평행사변형

 

2. AB, AC 변을 이용한 평행 사변형

 

3. BC, AC 변을 이용한 평행 사변형

 

평행사변형의 둘레 공식은 두 변의 길이 * 2이기 때문에,

 

이미 구해진 두 변의 길이가 가장 큰 경우와

 

가장 작은 경우를 빼서 곱하기 2를 해주면 답이 되겠습니다.

 

두 점 사이의 거리는 피타고라스 정리를 이용해서 구합니다.

 

코드

---

#include <iostream>
#include <cmath>
#include <algorithm>
#define x first
#define y second
using namespace std;

//점 간의 거리 구하기
inline double GetDistance(pair<int, int> const &A, pair<int, int> const &B)
{
    return sqrt(pow((A.x - B.x), 2) + pow((A.y - B.y), 2));
}

//세 점이 평행한 선에 있는지 확인
bool IsImpossible(pair<int, int> const &A, pair<int, int> const &B, pair<int, int> const &C)
{
    int result = A.x * B.y + B.x * C.y + C.x * A.y - (B.x * A.y + C.x * B.y + A.x * C.y);
    if(result == 0) return true;
    return false;
}

int main() 
{
    pair<int, int> a, b, c;
    scanf("%d %d %d %d %d %d", &a.x, &a.y, &b.x, &b.y, &c.x, &c.y);
    
    double AB = GetDistance(a, b);
    double BC = GetDistance(b, c);
    double AC = GetDistance(a, c);
    
    if(IsImpossible(a, b, c)) 
    {
        printf("-1.0");
        return 0;
    }
    
    printf("%.10lf", 2 * (max(max(AB + BC, AB + AC), BC + AC) - min(min(AB + BC, AB + AC), BC + AC)));
    
    
	return 0;
}

 

그 외

---