C++で与えられた点から作成できる四角形の数を求める方法

四角形とは？

四角形（クアドララテラル）とは、ユークリッド平面上で4つの頂点と4つの辺を持つ多角形のことを指します。「4-gon」という呼び方もあり、正方形や長方形なども四角形の一種に含まれます。

本記事では、与えられた点から作成できる四角形の数を求める手法について解説します。この問題では、直交座標系（XY平面）上に与えられた4つの点 (x, y) を用いて、いくつの四角形を構成できるかを求めます。まず、具体的な入力例と出力例を見てみましょう。

入力 : A( -2, 8 ), B( -2, 0 ), C( 6, -1 ), D( 0, 8 )
出力 : 1
説明 : 作成できる四角形は1つだけ（ ABCD ）

入力 : A( 1, 8 ), B( 0, 1 ), C( 4, 0 ), D( 1, 2 )
出力 : 3
説明 : 3つの四角形が作成可能（ABCD）、（ABDC）、（ADBC）

解法のアプローチ

• まず、4点のうち3点が同一直線上（コリニア）に存在するかどうかを確認します。存在する場合、その点からは四角形を作成できません。
• 次に、4点のうち2点が同一の座標であるかどうかを確認します。同一の場合も、四角形を作成することはできません。
• 最後に、対角線が交差するかどうかを判定します。交差する場合、作成できる四角形は1つのみであり、これを凸四角形と呼びます。

交差の総数 = 1

一方、対角線が交差しない場合は、3つの異なる四角形を作成することができ、これを凹四角形と呼びます。

交差の総数 = 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;
}
// 2点が同一かどうかを判定
bool check_similar(Point A, Point B){
    // 同一の場合はfalseを返す＝四角形は作成不可
    if (A.x == B.x && A.y == B.y)
        return false;
    // 同一でない場合はtrueを返す
    return true;
}
// 3点の同一直線性（コリニア）を判定
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)
    // 任意の3点が同一直線上にあるかどうかを確認
    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 << "Number of quadrilaterals possible from the given points: 0";
        return 0;
    }
    // 2点が同一かどうかを確認
    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 << "Number of quadrilaterals possible from the given points: 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 << "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

コードの解説

このコードは以下のステップで理解できます。

• 任意の3点が同一直線上にあるかどうかを確認 → 該当する場合、四角形の数は 0
• 任意の2点が同一かどうかを確認 → 該当する場合、四角形の数は 0
• 線分が交差するかどうかを確認：
  • 交差する場合 → 四角形の数は 1
  • 交差しない場合 → 四角形の数は 3

まとめ

本記事では、与えられた4点から作成可能なすべての四角形を求める問題を解決しました。四角形の数が「3点の同一直線性」「点の重複」「対角線の交差」といった条件によってどのように変化するのかを理解できたと思います。ここではC++で実装しましたが、同じロジックはC、Java、Pythonなど他の言語でも簡単に記述できます。