题意: 在给出最多20个点的情况下,找出平行于坐标轴的正方形的个数,每个点只能用一次,
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4739
思路:就暴力就行了,因为不到20个点,而且整个的图形限制在100*100内,看别人的代码都是状态压缩,估计比赛的时候数据很弱吧,
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> using namespace std; #define maxn 30 typedef struct node{ int x,y; }p; p g[maxn]; bool vis[maxn]; bool cmp(node a,node b){ if(a.x < b.x) return true; else if(a.x == b.x){ if(a.y < b.y) return true; return false; } return false; } bool judge(node a,node b,node c,node d){ if(a.x == b.x && c.x == d.x){ if(a.y == c.y && b.y == d.y){ int len1 = b.y - a.y; int len2 = c.x - a.x; if(len1 == len2) return true; return false; } return false; } return false; } int main() { int n; while(~scanf("%d",&n)){ if(n == -1) break; for(int i = 0 ; i < n;i ++){ scanf("%d %d",&g[i].x,&g[i].y); } if(n<4) { printf("0\n"); continue; } else{ memset(vis, 0 , sizeof(vis)); sort(g,g+n,cmp); int ans = 0; for(int i = 0; i < n;i ++) for(int j = i + 1; j < n ;j ++) for(int k = j + 1; k < n ;k ++) for(int p = k + 1; p < n ;p ++){ if(!vis[i] && !vis[j] && !vis[k] && !vis[p]){ if(judge(g[i],g[j],g[k],g[p])){ ans += 4; vis[i] = 1,vis[j] = 1,vis[k] = 1,vis[p] = 1; } } } printf("%d\n",ans); } } return 0; }