快速找到和为0的四个数

Description

The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .

Input

The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 228 ) that belong respectively to A, B, C and D .

Output

For each input file, your program has to write the number quadruplets whose sum is zero.

Sample Input

6 -45 22 42 -16 -41 -27 56 30 -36 53 -37 77 -36 30 -75 -46 26 -38 -10 62 -32 -54 -6 45

Sample Output

5

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std ;
int sum1[16000005] ,sum2[16000005] ;
int a[4005] ,b[4005] ,c[4005],d[4005] ;
int n = 0 , t =0 ;
 // t = n^2
int Binary_Search(int key)
{
  int num = 0 ;
  int left = 0  , right = t- 1 ;
  while (left <right)
  {
    int mid = left + (right - left)/2 ;
    if(key <=sum2[mid])
    right = mid ;
    else
    left = mid + 1 ;
    
    
  }
  
  while(sum2[left] == key && left < t )
  {
    num ++ ;
    left ++ ;
   }
  return num ;
  
}
int main()
{
  int i ;
  int j ;
  while(scanf("%d",&n)!=EOF)
  {
    t = 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++)
      {
        sum1[t] = a[i]+ b[j] ;
        sum2[t] = c[i] + d[j] ;
        t++ ;
      }
    }
    sort(sum1, sum1 + t) ;
    sort(sum2 ,sum2 + t) ;
    int num = 0 ;
    for( i = t-1; i>=0 ;i--)
    {
      num+=Binary_Search(-sum1[i]);
    }
    
    printf("%d\n",num) ;
    
  }
  /*
  6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

  */
  return 0 ;
}