這是一個經典的C語言算法題目，題目是給出一個給定的圖形，根據這幅圖形裡的作標可以求出這幅圖形一共可有構成多少個正方形。
例如下面這個圖形：
下面是解題思路：首先采用組合算法，得出這些頂點一共能構成多少個有四個頂點構成的四邊形，並列出每一個四邊形，然後用一個子函數對這四邊形進行判斷，若是正方形就加一，這樣就可以得出一共含有多少個正方形。
具體代碼：
#include<stdio.h>
#include<math.h>
/*輸入的圖形的頂點數量,一定要輸入正確的頂點數量,修改這個值可以得到不同的點情況下的
正方形數量*/
#define N 13
#define B ((N*(N-1)*(N-2)*(N-3))/(4*3*2))
typedef struct{
int x;
int y;
}Point;
typedef struct{
Point a[4];
}Squre;
Point dian[N];
Point queue[4]; /*存放矩形坐標*/
Squre tmp;
int k=0;
int top=0;
void comb(int s,int n,int m);
int function(Squre s);
int main(void){
int i=0;
int num=(int)B;
printf("%d",num);
for(i=0;i<N;i++){
printf("\nplease input the %d zuo biao :",i+1);
scanf("%d %d",&dian[i].x,&dian[i].y);
}
comb(0,N,4);
printf("the sum of sibianxing are %d\n",k);
getch();
return 0;
}
/*判斷是不是正方形，若是返回1，否則返回0*/
int function(Squre s){
int e,b,c,d,k;
e=pow((s.a[0].x-s.a[1].x),2)+pow((s.a[0].y-s.a[1].y),2);
b=pow((s.a[0].x-s.a[2].x),2)+pow((s.a[0].y-s.a[2].y),2);
if(e>b){ /*e作為對角線存在*/
c=pow((s.a[2].x-s.a[1].x),2)+pow((s.a[1].y-s.a[2].y),2);
d=pow((s.a[3].x-s.a[1].x),2)+pow((s.a[3].y-s.a[1].y),2);
k=pow((s.a[0].x-s.a[3].x),2)+pow((s.a[0].y-s.a[3].y),2);
if((b==c)&&(c==d)&&(d==k)&&(k==b)&&(e==(b+c)))
return 1;
}else if(e==b){
c=pow((s.a[1].x-s.a[3].x),2)+pow((s.a[1].y-s.a[3].y),2);
d=pow((s.a[2].x-s.a[3].x),2)+pow((s.a[2].y-s.a[3].y),2);
k=pow((s.a[1].x-s.a[2].x),2)+pow((s.a[1].y-s.a[2].y),2);
if((e==c)&&(c==d)&&((e+b)==k))
return 1;
}else { /*b作為對角線存在*/
c=pow((s.a[2].x-s.a[1].x),2)+pow((s.a[1].y-s.a[2].y),2);
d=pow((s.a[3].x-s.a[2].x),2)+pow((s.a[3].y-s.a[2].y),2);
k=pow((s.a[0].x-s.a[3].x),2)+pow((s.a[0].y-s.a[3].y),2);
if((e==c)&&(c==d)&&(d==k)&&(k==e)&&(b==(e+c)))
return 1;
}
return 0;
}
/*組合算法：用於得到可能構成正方形的矩形集合
m代表選取的個數就是組合數C(m,n),從n中選取m個點
並返回正方形數量*/
void comb(int s,int n,int m)
{
int i,j=0;
if(s>n) return ;
if(top==m) {
for(i=0;i<m;i++){
tmp.a[i]=queue[i];
}
j=function(tmp);
if(j==1){
k++;
}
return ;
}
queue[top++]=dian[s];
comb(s+1,n,m);
top--;
comb(s+1,n,m);
}
