hdu 6055 Regular polygon

hdu 6055 Regular polygon"/>

hdu 6055 Regular polygon

题意：给出n个点的坐标（均为整数），求能够组成的正多边形的个数

题目思路：都是整数点，那么组成的正多边形只能为正方形，每次枚举两个点，判断是否存在另外的两个点能够组成正方形。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<algorithm>
#define MAXSIZE 1005using namespace std;struct node
{int x,y;
}p[MAXSIZE];int vis[MAXSIZE][MAXSIZE];int solve(int p1,int p2)
{int x = p[p1].x - p[p2].x;int y = p[p1].y - p[p2].y;int ans=0;if(p[p1].x-y>=0 && p[p1].y+x>=0 && p[p2].x-y>=0 && p[p2].y+x>=0 && vis[p[p1].x-y][p[p1].y+x] && vis[p[p2].x-y][p[p2].y+x])ans++;if(p[p1].x+y>=0 && p[p1].y-x>=0 && p[p2].x+y>=0 && p[p2].y-x>=0 && vis[p[p1].x+y][p[p1].y-x] && vis[p[p2].x+y][p[p2].y-x])ans++;return ans;
}int main()
{int n,x,y;while(scanf("%d",&n)!=EOF){int ans = 0;memset(vis,0,sizeof(vis));for(int i=0;i<n;i++){scanf("%d%d",&x,&y);vis[x+200][y+200] = 1;p[i].x = x+200;p[i].y = y+200;}for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){ans += solve(i,j);}}ans /= 4;printf("%d\n",ans);}return 0;
}

转载于:.html