rendered paste body#include <stdio.h>#include <string.h>#include <stdlib.h>int n;int A[4000], B[4000], C[4000], D[4000];int AB[16000000], CD[16000000], TMP[8000];unsigned long long int zerosums;inline int max( int a, int b ) { return a > b ? a : b; }inline void read_data(){ scanf( "%d", &n ); int i; for( i = 0; i < n; i++ ) { scanf( "%d %d %d %d", &A[i], &B[i], &C[i], &D[i] ); }}inline void merge( int *arr, int l, int m, int r ){ int i = 0, j = l; while( j <= m ) TMP[i++] = arr[j++]; i = 0; int k = l; while( (k < j) && (j <= r) ) if( TMP[i] <= arr[j] ) arr[k++] = TMP[i++]; else arr[k++] = arr[j++]; while( k < j ) arr[k++] = TMP[i++];}inline void qsort_array( int *arr, int l, int r ){ int i=l, j=r; int x=arr[(l+r)/2]; // Aufteilung while (i<=j) { while (arr[i]<x) i++; while (arr[j]>x) j--; if (i<=j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; j--; } } // Rekursion if (l<j) qsort_array(arr, l, j); if (i<r) qsort_array(arr, i, r); }inline void process_data(){ qsort_array( A, 0, n-1 ); qsort_array( B, 0, n-1 ); qsort_array( C, 0, n-1 ); qsort_array( D, 0, n-1 ); int i, j, len; for( i = 0; i < n; i++ ) for( j = 0; j < n; j++ ) { AB[n*i + j] = A[i] + B[j]; CD[n*i + j] = C[i] + D[j]; } /* merge n sorted lists of length n */ for( len = n; len < n*n; len += len ) for( i = (n*n)-1-len; i >= 0; i -= 2*len ) { merge( AB, max(i-len+1, 0), i, len+i ); merge( CD, max(i-len+1, 0), i, len+i ); }}inline void count_sums(){ zerosums = 0; int i = 0, j = n*n-1; while( i < n*n && j >= 0 ) { int ab_hits = 0, cd_hits = 0; while( (AB[i] + CD[j] != 0) && (i < n*n) && (j >= 0) ) { if( AB[i] + CD[j] < 0 ) i++; else j--; } if( j < 0 || i >= n*n ) break; //printf("found 0: i = %d, j = %d, AB[i] = %d, CD[j] = %d", i, j, AB[i], CD[j] ); while( i < n*n ) if( AB[i] + CD[j] == 0 ) { ab_hits++; i++; } else break; i--; while( j >= 0 ) if( AB[i] + CD[j] == 0 ) { cd_hits++; j--; } else { break; } i++; zerosums += (ab_hits*cd_hits); //printf( " (%d*%d possibilities)\n", ab_hits, cd_hits ); }}int main( int argc, char *argv[] ){ read_data(); if( n > 0 ) { process_data(); count_sums(); printf( "%llu\n", zerosums ); } else { printf( "0\n" ); } return 0;}