poj 2785

#include <stdio.h>
#include <algorithm>
#define N 4000
using namespace std;

int a[N],b[N],c[N],d[N],ab[N*N],cd[N*N];

int main()
{
int n,ans,i,j,k;
while(scanf("%d",&n)!=EOF)
{
k=0;
for(i=0;i<n;i++)
scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
ab[k]=a[i]+b[j];
cd[k]=-c[i]-d[j];
k++;
}
sort(cd,cd+n*n);
for( ans=0,i=0;i<n*n;i++)
{
int left=0,right=n*n-1,mid;
while(left<=right)
{
mid=(left+right)/2;
if(ab[i]==cd[mid])
{
ans++;
for(k=mid+1;k<n*n;k++)
if(ab[i]==cd[k]) ans++; else break;
for(k=mid-1;k>=0;k--)
if(ab[i]==cd[k]) ans++; else break;
break;
}
else if(ab[i]<cd[mid]) right=mid-1;
else left=mid+1;
}
}
printf("%d ",ans);
}
}