Plite
전자오락 공방
Plite
전체 방문자
오늘
어제
  • 분류 전체보기 (274)
    • 프로젝트 (18)
      • 완성 프로젝트 (3)
      • 프로젝트 진행 내역 (15)
    • 공부 및 정리 (241)
      • 백준 코드 (222)
      • C++ (8)
      • DirectX (2)
      • Unreal Engine (6)
      • 프로그래밍 패턴 (3)
    • 기타 (12)
      • 기타 주저리 (10)
    • 게임과 취미 (1)
    • 대문 (1)

블로그 메뉴

  • 홈
  • 프로젝트
  • 취미, 일상
  • 백준 프로필

공지사항

  • [Read Me]
  • 제 블로그에 방문하신 것을 환영합니다.

인기 글

태그

  • 기하
  • 백준
  • C++
  • 세그먼트 트리
  • LCA
  • KMP
  • 정수론
  • 조합론
  • 브루트포스
  • 위상 정렬
  • 트리
  • 동적계획법
  • SCC
  • 투포인터
  • 큐
  • 그래프
  • UC++
  • 유니온 파인드
  • 누적합
  • 최소 스패닝 트리
  • 분할정복
  • 백트래킹
  • 정렬
  • 구현
  • 우선순위큐
  • 트라이
  • 스택
  • 이분탐색
  • 수학
  • 문자열

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Plite

전자오락 공방

[C++]백준 - 1064번 문제
공부 및 정리/백준 코드

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

2022. 5. 19. 11:45

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

 

1064번: 평행사변형

평행사변형은 평행한 두 변을 가진 사각형이다. 세 개의 서로 다른 점이 주어진다. A(xA,yA), B(xB,yB), C(xC,yC) 이때, 적절히 점 D를 찾아서 네 점으로 평행사변형을 만들면 된다. 이때, D가 여러 개 나

www.acmicpc.net

 

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로 세 점의 방향성 판별하기

0. 들어가기 전에 첫 알고리즘 포스트입니다. 이번에 쓸 내용은 CCW입니다. 원래는 기하 알고리즘들을 전반적으로 다루려고 했는데 생각보다 글이 길어져서 CCW만 쓰게 되었습니다. 본 글의 내용

degurii.tistory.com

 

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

 

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

 

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;
}

 

그 외


 

저작자표시 (새창열림)

'공부 및 정리 > 백준 코드' 카테고리의 다른 글

[C++]백준 - 10815번 문제  (0) 2022.07.26
[C++]백준 - 1790번 문제  (0) 2022.07.25
[C++]백준 - 7662번 문제  (0) 2022.01.02
[C++]백준 - 5525번 문제  (0) 2022.01.01
[C++]백준 - 15973번 문제  (0) 2021.12.31
    '공부 및 정리/백준 코드' 카테고리의 다른 글
    • [C++]백준 - 10815번 문제
    • [C++]백준 - 1790번 문제
    • [C++]백준 - 7662번 문제
    • [C++]백준 - 5525번 문제
    Plite
    Plite
    개발 일지, 게임 이야기 등을 적어두는 공간입니다.

    티스토리툴바