学步园

//枚举 + HASH<br /> //和2002很像，这次是找平行四边形，规模1000，因此只能采用O(N^2)<br /> //一开始我是想到枚举3个点确定2条边，由这2条边确定第4的点，再用HASH判断是否存在，但是O(n^3)绝对TLE<br /> //再想了一下，发现可以枚举对角线，进而确定中点，2条直线如果中点相同，那么必定确定一个平行四边形<br /> //根据这个性质来对边的中点值进行HASH就可以了，发现一个中点值就插入，并计数，最后答案就是这些计数的总和<br /> //效率的关键是HASH函数的设计，我用折叠法的HASH随便搞了一通，再随便确定一个MAXHASH，结果居然有766MS<br /> //刷到第一版，哈哈！<br /> #include<iostream><br /> using namespace std;<br /> const int MAXHASH = 7345787;<br /> int head[MAXHASH],next[1000003];<br /> int m,ans;<br /> struct coord<br /> {<br /> long x,y;<br /> }P[1005];<br /> struct midPoint<br /> {<br /> long x,y,cnt;//cnt计算出现的次数<br /> }G[1000003];<br /> int hash(int x,int y)//拿折叠法的HASH乱改了一下。。。<br /> {<br /> int h = 0;<br /> h = ((x<<2) + (x>>4)) ^ (y<<10);<br /> h = h % MAXHASH;<br /> h = h < 0 ? h + MAXHASH : h;<br /> return h;<br /> }<br /> void insert(int x,int y)<br /> {<br /> int h = hash(x,y);<br /> bool Find = 0;<br /> for(int e = head[h];e != -1;e = next[e])<br /> {<br /> if(G[e].x == x && G[e].y == y)<br /> {<br /> Find = 1;<br /> ans += G[e].cnt++;<br /> break;<br /> }<br /> }<br /> if(!Find)<br /> {<br /> G[m].x = x;<br /> G[m].y = y;<br /> G[m].cnt = 1;<br /> next[m] = head[h];<br /> head[h] = m++;<br /> }<br /> }<br /> int main()<br /> {<br /> //freopen("in.txt","r",stdin);<br /> int t,n,x,y;<br /> scanf("%d",&t);<br /> while(t--)<br /> {<br /> scanf("%d",&n);<br /> memset(head,-1,sizeof(head));<br /> memset(G,0,sizeof(G));<br /> m = ans = 0;<br /> for(int i = 0;i < n;++i)<br /> scanf("%ld%ld",&P[i].x,&P[i].y);</p> <p> for(int i = 0;i < n;++i)<br /> for(int j = i + 1;j < n;++j)//枚举边<br /> insert(P[i].x + P[j].x,P[i].y + P[j].y);</p> <p> printf("%d/n",ans);<br /> }<br /> return 0;<br /> }