首页 > 代码库 > HDU 6055 - Regular polygon

HDU 6055 - Regular polygon

/*HDU 6055 - Regular polygon [ 分析,枚举 ]题意:	给出 x,y 都在 [-100, +100] 范围内的 N 个整点,问组成的正多边形的数目是多少	N <= 500分析:	分析可知,整点组成的正多边形只能是正方形	故枚举两个点,验证剩下两个点的位置		坑点: 由于点的范围是 [-100, +100],故经过计算得出的点的范围可能是 [-300,+300],注意越界编码时长:46分钟(-1)*/#include <bits/stdc++.h>using namespace std;int n;bool mp[1005][1005];int ans;int x[505], y[505];void solve(int x1, int y1, int x2, int y2){	if (x1 > x2) swap(x1, x2), swap(y1, y2);	int x3, y3, x4, y4;	x3 = x1 - (y2-y1);	y3 = y1 + x2-x1;	x4 = x2 - (y2-y1);	y4 = y2 + x2-x1;	if (mp[x3][y3] && mp[x4][y4]) ans++;	x3 = x1 + y2-y1;	y3 = y1 - (x2-x1);	x4 = x2 + y2-y1;	y4 = y2 - (x2-x1);		if (mp[x3][y3] && mp[x4][y4]) ans++;}int main(){	while (~scanf("%d", &n))	{		memset(mp, 0, sizeof(mp));		for (int i = 1; i <= n; i++)		{			scanf("%d%d", &x[i], &y[i]);			x[i] += 500, y[i] += 500;			mp[x[i]][y[i]] = 1;		}		ans = 0;		for (int i = 1; i <= n; i++)			for (int j = i+1; j <= n; j++)				solve(x[i], y[i], x[j], y[j]);		printf("%d\n", ans/4);	}} 

  

HDU 6055 - Regular polygon