題意簡單,就是找四個(gè)數(shù)的和為零.先把前兩列的和算出來,O(n^2),存到hash表中,再把后兩列的兩兩和算出來,在hash表中找相反數(shù).用線性探測(cè)法就可以解決該問題了.
/**//*Source CodeProblem: 2785 User: y09shendazhi
Memory: 160132K Time: 2610MS
Language: G++ Result: Accepted
Source Code*/
#include <iostream>
#include<stdio.h>
using namespace std;
const int size=20345677;
int hash[size];
int sum[size];
const int key=1777;
const int MAX=1000000000;
void Insert(int num)
{
int temp=num;
num=(num+MAX)%size;
while(hash[num]!=MAX && hash[num]!=temp)
num=(key+num)%size;
hash[num]=temp;
sum[num]++;
}
int Find(int num)
{
int temp=num;
num=(num+MAX)%size;
while(hash[num]!=MAX && hash[num]!=temp)
num=(num+key)%size;
if(hash[num]==MAX)
return 0;
else
return sum[num];
}
int main()
{
int n;
int i,j;
int a[4005],b[4005],c[4005],d[4005];
scanf("%d",&n);
int ans=0;
for(i=0;i<n;i++)
{
scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
}
for(i=0;i<size;i++)
{
hash[i]=MAX;
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
Insert(a[i]+b[j]);
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
ans+=Find(-(c[i]+d[j]));
}
printf("%d\n",ans);
return 0;
}