题意:
给了N个点(N<=20)..问最多能组成多少个正方形(要求边平行与坐标轴)
题解:
直接暴力DFS就行了..每次确定一个正方形.再深入..更新答案..
Program:
#include<iostream> #include<stack> #include<queue> #include<stdio.h> #include<algorithm> #include<string.h> #include<cmath> #define ll long long #define oo 1000000007 #define eps 1e-5 #define MAXN 3005 #define MAXM 3000005 using namespace std; struct node { int x,y; }P[32]; bool used[32]; int num,ans,n; void dfs(int i) { int j,k,h,w1,w2; ans=max(ans,num); for (;i<n;i++) { if (used[i]) continue; used[i]=true; for (j=i+1;j<n;j++) { if (used[j] || P[i].y==P[j].y || P[i].x!=P[j].x) continue; used[j]=true; h=abs(P[i].y-P[j].y),w1=-1; for (w1=0;w1<n;w1++) if (P[w1].x==P[i].x+h && P[w1].y==P[i].y && !used[w1]) break; if (w1==n) { used[j]=false; continue; } used[w1]=true; for (w2=0;w2<n;w2++) if (P[w2].x==P[j].x+h && P[w2].y==P[j].y && !used[w2]) break; if (w2==n){ used[j]=used[w1]=false; continue; } used[w2]=true; num+=4; dfs(i+1); used[j]=used[w1]=used[w2]=false; num-=4; } used[i]=false; } return; } int main() { int i; while (~scanf("%d",&n) && n!=-1) { for (i=0;i<n;i++) scanf("%d%d",&P[i].x,&P[i].y); ans=num=0,memset(used,false,sizeof(used)); dfs(0); printf("%d\n",ans); } return 0; }