http://acm.hdu.edu.cn/showproblem.php?pid=6055
【题意】
给定n个格点，问有多少个正多边形
【思路】
- 因为是格点，只可能是正方形
- 枚举正方形的对角线，因为有两条对角线，最后答案要/2
- 也可以枚举正方形的边，因为有四条边，答案要/4
- 看当前对角线确定的正方形是否存在，用几何知识求出目标点的坐标，然后二分查找目标点是否存在
【Accepted】
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include<iostream>
#include <vector>
using namespace std ;
#define eqs 1e-9
struct node
{
double x , y ;
} p[] ;
bool cmp(node a,node b)
{
return ( a.x < b.x || ( a.x == b.x && a.y < b.y ) ) ;
}
bool judge(double x,double y,int n)
{
int low = , mid , high = n- ;
while( low <= high )
{
mid = (low + high) / ;
if( fabs(p[mid].x-x) < eqs && fabs(p[mid].y-y) < eqs )
return true ;
else if( p[mid].x-x > eqs || ( fabs(p[mid].x-x) < eqs && p[mid].y-y > eqs ) )
high = mid - ;
else
low = mid + ;
}
return false ;
}
int main()
{
int n,num;
double x,xx,y,yy;
while(scanf("%d", &n)!=EOF&&n)
{
num = ;
for(int i = ; i < n ; i++)
{
cin>>p[i].x>>p[i].y;
}
sort(p,p+n,cmp) ;
for(int i = ; i < n ; i++)
{
for(int j = i+ ; j < n ; j++)
{
if( i == j ) continue ;
x = (p[i].x+p[j].x)/ ;
y = (p[i].y+p[j].y)/ ;
xx = p[i].x - x ;
yy = p[i].y - y ;
if( judge(x+yy,y-xx,n) && judge(x-yy,y+xx,n) )
{
num++ ;
}
}
}
cout<<num/<<endl;
}
return ;
}