Meet in the middle and binary search algorithm is used to solve this problem.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#include <iostream> #include <string.h> #include <algorithm> #include <map> using namespace std; int A[4001]; int B[4001]; int C[4001]; int D[4001]; int E[16008001]; int F[16008001]; //map<int,int> mp; struct myHash { int value; int valueOccuredNumberOfTimes; }FF[16008001]; int main() { int t,n,x,cnt,a; int low,mid,high; int k,l; cin>>t; while(t--) { cin>>n; cnt=0; //mp.clear(); for(int i=0;i<n;i++) { cin>>A[i]>>B[i]>>C[i]>>D[i]; } k=0; l=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { E[k++]=A[i]+B[j]; F[l++]=C[i]+D[j]; } } sort(F,F+l); FF[0].value = F[0]; FF[0].valueOccuredNumberOfTimes=1; int ind=0; for(int i=1;i<l;i++) { if(F[i]==F[i-1]) { FF[ind].valueOccuredNumberOfTimes+=1; } else { ind+=1; FF[ind].value=F[i]; FF[ind].valueOccuredNumberOfTimes=1; } } ind+=1; for(int i=0;i<k;i++) { x = E[i]*(-1); low=0; high=ind; while((high-low)>1) { mid=(low+high)/2; if(FF[mid].value<x) low=mid; else high=mid; } if(FF[low].value==x) { cnt+=FF[low].valueOccuredNumberOfTimes; //cout<<FF[low].value<<" "<<FF[low].valueOccuredNumberOfTimes<<"\n"; } else if(FF[high].value==x) { cnt+=FF[high].valueOccuredNumberOfTimes; } } cout<<cnt<<"\n"; if(t) cout<<"\n"; } return 0; } |