Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 주어진 좌표점으로 만들 수 있는 사변형 개수 구하기

사변형(quadrilateral)은 유클리드 평면 기하학에서 네 개의 꼭짓점과 네 개의 변을 가진 다각형을 의미합니다. 흔히 '4각형(4-gon)'이라고도 부르며, 경우에 따라 정사각형처럼 특정한 형태의 이름으로 불리기도 합니다.

이 글에서는 주어진 점들로 만들 수 있는 사변형의 개수를 구하는 방법을 알아보겠습니다. 이 문제는 데카르트 좌표 평면상의 네 개의 점 (x, y)가 주어졌을 때, 이 점들을 이용해 만들 수 있는 사변형이 총 몇 개인지 구하는 것이 목표입니다.

입력 예시

입력 : A( -2, 8 ), B( -2, 0 ), C( 6, -1 ), D( 0, 8 )
출력 : 1
설명 : 하나의 사변형(ABCD)을 만들 수 있습니다.
입력 : A( 1, 8 ), B( 0, 1 ), C( 4, 0 ), D( 1, 2 )
출력 : 3
설명 : 세 개의 사변형(ABCD), (ABDC), (ADBC)을 만들 수 있습니다.

문제 해결 접근 방식

  • 먼저 4개의 점 중 3개가 한 직선 위에 있는지(공선 여부) 확인합니다. 만약 3개의 점이 일직선상에 있다면 어떤 사변형도 만들 수 없습니다.

  • 다음으로 4개의 점 중 2개가 서로 같은 점인지 확인합니다. 같은 점이 존재하면 역시 사변형을 만들 수 없습니다.

  • 마지막으로 대각선이 서로 교차하는지 확인합니다. 대각선이 교차한다면 단 하나의 사변형만 만들 수 있으며, 이를 볼록 사변형(convex quadrilateral)이라고 부릅니다.

교차하는 선분의 총 개수 = 1

반대로 대각선이 교차하지 않는다면 세 가지 형태의 사변형을 만들 수 있으며, 이를 오목 사변형(concave quadrilateral)이라고 부릅니다.

교차하는 선분의 총 개수 = 0

C++ 구현 코드

#include <iostream>
using namespace std;
struct Point{ // 좌표점
    int x;
    int y;
};
int check_orientation(Point i, Point j, Point k){
    int val = (j.y - i.y) * (k.x - j.x) - (j.x - i.x) * (k.y - j.y);
    if (val == 0)
       return 0;
    return (val > 0) ? 1 : 2;
}
// 두 선분이 교차하는지 확인
bool check_Intersect(Point A, Point B, Point C, Point D){
    int o1 = check_orientation(A, B, C);
    int o2 = check_orientation(A, B, D);
    int o3 = check_orientation(C, D, A);
    int o4 = check_orientation(C, D, B);
    if (o1 != o2 && o3 != o4)
       return true;
    return false;
}
// 두 점이 같은지 확인
bool check_similar(Point A, Point B){
   // 같은 점이 발견되면 false 반환 → 사변형 생성 불가
    if (A.x == B.x && A.y == B.y)
       return false;
   // 같은 점이 없으면 true 반환
    return true;
}
// 세 점의 공선 여부 확인
bool check_collinear(Point A, Point B, Point C){
    int x1 = A.x, y1 = A.y;
    int x2 = B.x, y2 = B.y;
    int x3 = C.x, y3 = C.y;
    if ((y3 - y2) * (x2 - x1) == (y2 - y1) * (x3 - x2))
       return false;
    else
       return true;
}
// 메인 함수
int main(){
   struct Point A,B,C,D;
   A.x = -2, A.y = 8;// A(-2, 8)
   B.x = -2, B.y = 0;// B(-2, 0)
   C.x = 6, C.y = -1;// C(6, -1)
   D.x = 0, D.y = 8;// D(0, 8)
   // 세 점이 공선인지 확인
   bool flag = true;
   flag = flag & check_collinear(A, B, C);
   flag = flag & check_collinear(A, B, D);
   flag = flag & check_collinear(A, C, D);
   flag = flag & check_collinear(B, C, D);
   // 공선인 점들이 발견된 경우
   if (flag == false){
       cout << "주어진 점으로 만들 수 있는 사변형의 개수: 0";
       return 0;
   }
   // 두 점이 같은지 확인
   bool same = true;
   same = same & check_similar(A, B);
   same = same & check_similar(A, C);
   same = same & check_similar(B, D);
   same = same & check_similar(C, D);
   same = same & check_similar(A, D);
   same = same & check_similar(B, C);
   // 같은 점이 존재하는 경우
   if (same == false){
       cout << "주어진 점으로 만들 수 있는 사변형의 개수: 0";
   return 0;
   }
   // 대각선이 교차하는지 확인
    flag = true;
   if (check_Intersect(A, B, C, D))
       flag = false;
   if (check_Intersect(A, C, B, D))
       flag = false;
   if (check_Intersect(A, B, D, C))
       flag = false;
   if (flag == true)
       cout << "주어진 점으로 만들 수 있는 사변형의 개수: 3";
   else
       cout << "주어진 점으로 만들 수 있는 사변형의 개수: 1";
   return 0;
}

실행 결과

주어진 점으로 만들 수 있는 사변형의 개수 : 1

코드 상세 설명

위 코드는 다음과 같은 단계로 이해할 수 있습니다.

  • 세 점이 공선(일직선상)인지 확인합니다. 공선인 경우가 있다면 사변형 개수는 0입니다.

  • 두 점이 서로 같은지 확인합니다. 같은 점이 존재하면 사변형 개수는 0입니다.

  • 선분이 교차하는지 확인합니다.

    • 교차하는 경우 → 사변형 개수 : 1

    • 교차하지 않는 경우 → 사변형 개수 : 3

마무리

이 글에서는 주어진 4개의 점으로 만들 수 있는 모든 사변형을 찾는 문제를 해결해 보았습니다. 사변형의 개수가 점들의 공선성, 선분의 교차 여부, 그리고 방향(orientation) 판정에 따라 어떻게 달라지는지 살펴보았습니다. 또한 이를 C++ 프로그램으로 구현했으며, 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다.