POJ(PKU) 4 Values whose Sum is 0

半分全列挙するだけ。

一発ACだった。

#include <cstdio>
#include <algorithm>
using namespace std;

int a[4003],b[4003],c[4003],d[4003];
int e[16000005];
int n;
int main(){
  
  scanf("%d",&n);
  
  for(int i = 0;i < n;i++){
    scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
  }
  
  for(int i = 0;i < n;i++){
    for(int j = 0;j < n;j++){
      e[i*n+j] = a[i] + b[j];
    }
  }
  
  sort(e,e + n*n);
  long long int ans = 0;
  for(int i = 0;i < n;i++){
    for(int j = 0;j < n;j++){
      int k = -(c[i] + d[j]);
      ans += upper_bound(e,e+n*n,k) - lower_bound(e,e+n*n,k);
    }
  }
  
  printf("%lld\n",ans);
  
  return 0;
  
}