hdu 4739

时间:2023-03-09 19:30:14
hdu 4739

一个超级超级水的题,不明白当时比赛的时候没有出来;

思路很简单,dfs暴力一下就行,枚举每个顶点,题目一共才20个点,就是20^4方的时间复杂度,完全可以承受;

代码:

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; struct node
{
int x,y;
} no[];
bool use[];
int ans,num,n; void dfs(int i)
{
ans=max(num,ans);
for(; i<n; i++)
{
if(use[i])continue;
use[i]=;
for(int j=; j<n; j++)
{
if(use[j]||no[j].x!=no[i].x) continue;
use[j]=;
int l=no[i].y-no[j].y;
for(int k=; k<n; k++)
{
if(use[k]||no[k].y!=no[j].y||(no[k].x-no[j].x)!=l) continue;
use[k]=;
for(int m=; m<n; m++)
{
if(use[m]||no[m].x!=no[k].x||(no[m].y-no[k].y)!=l)continue;
use[m]=;
num+=;
dfs(i+);
use[m]=;
num-=;
}
use[k]=;
}
use[j]=;
}
use[i]=;
}
} int main()
{
while(scanf("%d",&n)&&n!=-)
{
memset(use,,sizeof use);
ans=num=;
for(int i=; i<n; i++)
scanf("%d%d",&no[i].x,&no[i].y);
if(n<){puts("");continue;}
dfs();
printf("%d\n",ans);
}
return ;
}