사변형은 유클리드 평면 기하학에서 4개의 꼭짓점과 4개의 모서리가 있는 다각형을 형성합니다. 사각형 등의 이름. 사변형의 다른 이름에 포함되며 때로는 정사각형, 표시 스타일 등으로도 알려져 있습니다.
이 기사에서는 주어진 점에서 가능한 사변형의 수를 찾는 방법에 대해 설명합니다. 이 문제에서는 직교 평면에서 제공된 네 점( x, y )으로 만들 수 있는 사변형이 몇 개인지 알아낼 필요가 있습니다. 다음은 주어진 문제에 대한 예입니다 -
Input : A( -2, 8 ), B( -2, 0 ), C( 6, -1 ), D( 0, 8 ) Output : 1 Explanation : One quadrilateral can be formed ( ABCD )
Input : A( 1, 8 ), B( 0, 1 ), C( 4, 0 ), D( 1, 2 ) Output : 3 Explanation : 3 quadrilaterals can be formed (ABCD), (ABDC) and (ADBC).
해결 방법 찾기
-
먼저 4개의 점 중 3개가 동일선상에 있는지 확인하고 동일선상에 있으면 사변형이 점으로 형성될 수 없습니다. .
-
그 후 4점 중 2점이 동일한지 여부를 확인하고 동일하면 사변형을 만들 수 없습니다. .
-
이제 대각선이 교차하는지 여부를 확인합니다. 그렇다면 만들 수 있는 사변형은 하나입니다. 볼록 사변형이라고 함 .
총 교차 수 =1
대각선이 교차하지 않으면 오목한 사각형이라고 하는 세 개의 가능한 사각형이 형성될 수 있습니다.
총 교차 수 =0
예시
#include <iostream>
using namespace std;
struct Point{ // points
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;
}
// checking whether line segments intersect
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;
}
// checking whether 2 points are same
bool check_similar(Point A, Point B){
// If found similiar then we are returning false that means no quad. can be formed
if (A.x == B.x && A.y == B.y)
return false;
// returning true for not found similiar
return true;
}
// Checking collinearity of three points
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;
}
// main function
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)
// Checking whether any 3 points are collinear
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 points found collinear
if (flag == false){
cout << "Number of quadrilaterals possible from the given points: 0";
return 0;
}
// Checking if 2 points are same.
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 similiar point exist
if (same == false){
cout << "Number of quadrilaterals possible from the given points: 0";
return 0;
}
// checking whether diagonal intersect or not
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 << "Number of quadrilaterals possible from the given points: 3";
else
cout << "Number of quadrilaterals possible from the given points: 1";
return 0;
} 출력
Number of quadrilaterals possible from the given points : 1
위 코드 설명
이 코드는 다음 단계에서 이해할 수 있습니다 -
-
세 개의 점이 동일선상에 있는지 확인하고 그렇다면 쿼드의 수입니다. :0
-
두 점이 유사한지 확인하고 유사하면 쿼드의 수입니다. :0
-
선분의 교차 여부 확인:
-
그렇다면 쿼드의 수입니다. :1
-
아니오인 경우 쿼드의 수입니다. :3
-
결론
이 기사에서는 주어진 4개의 점으로 만들 수 있는 모든 가능한 사변형을 찾는 문제를 해결했습니다. 사변형의 수가 공선성, 교차 및 방향에 따라 어떻게 달라지는지 이해합니다. 우리는 또한 C++ 프로그램을 작성하는데 C, Java, python과 같은 다른 언어로 이 프로그램을 작성할 수 있습니다.