C 語言演算法：給定頂點集合求正方形個數

問題描述

給定平面上 N 個點的座標，求這些點能構成多少個正方形。例如下圖 13 個點的分佈：

解題思路

1. 組合枚舉：從 N 個點中任選 4 個點，共有 C(N,4) 種四邊形組合
2. 幾何判斷：對每組 4 點，判斷是否為正方形
3. 計數累加：符合條件者計數器加一

核心判斷邏輯

利用向量距離平方比較，避免浮點運算。四點 A,B,C,D 構成正方形的充要條件：

• 四邊長相等：AB = BC = CD = DA
• 對角線長相等且為邊長的 2 倍：AC = BD = 2 × AB

程式中透過排列組合嘗試不同點序，分情況檢驗對角線與邊長關係。

完整程式碼

#include <stdio.h>
#include <math.h>

#define N 13
#define B ((N*(N-1)*(N-2)*(N-3))/(4*3*2))  // C(N,4)

typedef struct { int x, y; } Point;
typedef struct { Point a[4]; } Square;

Point dian[N];
Point queue[4];
Square tmp;
int k = 0, top = 0;

void comb(int s, int n, int m);
int function(Square s);

int main(void)
{
    int i, num = (int)B;
    printf("總組合數: %d\n", num);
    for (i = 0; i < N; i++)
    {
        printf("請輸入第 %d 個座標 (x y): ", i+1);
        scanf("%d %d", &dian[i].x, &dian[i].y);
    }

    comb(0, N, 4);
    printf("正方形總數: %d\n", k);
    return 0;
}

int function(Square s)
{
    int e, b, c, d, k_val;
    e = (s.a[0].x-s.a[1].x)*(s.a[0].x-s.a[1].x) + (s.a[0].y-s.a[1].y)*(s.a[0].y-s.a[1].y);
    b = (s.a[0].x-s.a[2].x)*(s.a[0].x-s.a[2].x) + (s.a[0].y-s.a[2].y)*(s.a[0].y-s.a[2].y);

    if (e > b) {  // e 為對角線
        c = (s.a[2].x-s.a[1].x)*(s.a[2].x-s.a[1].x) + (s.a[2].y-s.a[1].y)*(s.a[2].y-s.a[1].y);
        d = (s.a[3].x-s.a[1].x)*(s.a[3].x-s.a[1].x) + (s.a[3].y-s.a[1].y)*(s.a[3].y-s.a[1].y);
        k_val = (s.a[0].x-s.a[3].x)*(s.a[0].x-s.a[3].x) + (s.a[0].y-s.a[3].y)*(s.a[0].y-s.a[3].y);
        if (b==c && c==d && d==k_val && k_val==b && e==(b+c)) return 1;
    }
    else if (e == b) {  // e,b 為邊
        c = (s.a[1].x-s.a[3].x)*(s.a[1].x-s.a[3].x) + (s.a[1].y-s.a[3].y)*(s.a[1].y-s.a[3].y);
        d = (s.a[2].x-s.a[3].x)*(s.a[2].x-s.a[3].x) + (s.a[2].y-s.a[3].y)*(s.a[2].y-s.a[3].y);
        k_val = (s.a[1].x-s.a[2].x)*(s.a[1].x-s.a[2].x) + (s.a[1].y-s.a[2].y)*(s.a[1].y-s.a[2].y);
        if (e==c && c==d && (e+b)==k_val) return 1;
    }
    else {  // b 為對角線
        c = (s.a[2].x-s.a[1].x)*(s.a[2].x-s.a[1].x) + (s.a[2].y-s.a[1].y)*(s.a[2].y-s.a[1].y);
        d = (s.a[3].x-s.a[2].x)*(s.a.a[3].x-s.a[2].x) + (s.a[3].y-s.a[2].y)*(s.a[3].y-s.a[2].y);
        k_val = (s.a[0].x-s.a[3].x)*(s.a[0].x-s.a[3].x) + (s.a[0].y-s.a[3].y)*(s.a[0].y-s.a[3].y);
        if (e==c && c==d && d==k_val && k_val==e && b==(e+c)) return 1;
    }
    return 0;
}

void comb(int s, int n, int m)
{
    if (s > n) return;
    if (top == m)
    {
        for (int i = 0; i < m; i++) tmp.a[i] = queue[i];
        if (function(tmp)) k++;
        return;
    }
    queue[top++] = dian[s];
    comb(s+1, n, m);
    top--;
    comb(s+1, n, m);
}

複雜度分析

• 時間複雜度：O(N^4)，僅適合 N ≤ 20 的小規模資料
• 空間複雜度：O(N)

大規模點集建議改用「以邊為基礎」或「向量分組」的 O(N^2 log N) 演算法。