POJ2002 Squares(二维点哈希)

?

题意：

给定n个点 判断这n个点可以构成多少正方形。

?

分析：

暴力枚举一条边的两个端点，然后根据全等三角形可以求出可以构成正方形的另外两个边的端点，然后判断这两个两存不存在。

因此首先要把所有的点哈希一下，然后依次暴力枚举，因此四条边都统计了一次 因此最后要除4.

?

代码如下：

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int mod = 10007; const int maxn = 1010; struct nod { int x,y; }; inline int read()//输入外挂 { char ch=getchar(); int x=0,f=1; while(ch>'9'||ch<'0') { if(ch=='-')f=-1; ch=getchar(); } while(ch<='9'&&ch>='0') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } struct hashmap { nod a[maxn]; int head[mod],next[maxn],cnt; void init() { cnt=0; memset(head,-1,sizeof(head)); memset(next,0,sizeof(next)); } bool find(nod val) { int tmp = (val.x*val.x+val.y*val.y)%mod; for(int i=head[tmp]; i!=-1; i=next[i]) if(a[i].x==val.x&&a[i].y==val.y) return true; return false; } void add(nod val) { int tmp = (val.x*val.x+val.y*val.y)%mod; for(int i=head[tmp]; i!=-1; i=next[i]) if(a[i].x==val.x&&a[i].y==val.y) return; a[cnt]=val; next[cnt]=head[tmp]; head[tmp]=cnt++; } } h; nod p[maxn]; int main() { int n; while(~scanf(%d,&n)) { if(n==0) break; h.init(); for(int i=0; i
       
        >= 2; printf(%d ,ans); } return 0; } 
       
      
     
    
   
  

?

?