4 Values whose Sum is 0　ｐｏｊ２７８５

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 2 ²⁸ ) 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

Hint

Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).

这道题刚拿到手的时候完全没思路，但是暴力绝逼超时，先是想着用ｓｅｔ后来发现不可行，二分尽然过了，，，，，

 1 #include <iostream>
 2 using namespace std;
 3 #include<string.h>
 4 #include<set>
 5 #include<stdio.h>
 6 #include<math.h>
 7 #include<queue>
 8 #include<map>
 9 #include<algorithm>
10 #include<cstdio>
11 #include<cmath>
12 #include<cstring>
13 #include <cstdio>
14 #include <cstdlib>
15 #include<cstring>
16 int a[4010],b[4010],c[4010],d[4010];
17 int a1[16000000],b1[16000000];
18 set<int>TM;
19 int main()
20 {
21     int t;
22     cin>>t;
23     for(int i=0;i<t;i++)
24         cin>>a[i]>>b[i]>>c[i]>>d[i];
25         int add=0;
26         for(int i=0;i<t;i++)
27             for(int j=0;j<t;j++)
28         {
29             b1[add]=(a[i]+b[j]);
30             a1[add++]=c[i]+d[j];
31         }
32         sort(b1,b1+add);
33         int sum=0;
34         for(int i=0;i<add;i++)
35         {
36             int tou=0,wei=add,zhongjian;
37             while(tou<=wei)
38             {
39                 zhongjian=(tou+wei)/2;
40                 if(a1[i]+b1[zhongjian]==0)
41                    {
42                        sum++;
43                 for(int j=zhongjian-1;j>=0;j--)
44                     {
45                     if(b1[j]!=b1[j+1])
46                     break;
47                      else
48                     sum++;
49                     }
50                 for(int j=zhongjian+1;j<add;j++)
51                    {
52                     if(b1[j]!=b1[j-1])
53                     break;
54                      else
55                     sum++;
56                    }
57                    break;
58                    }
59                    else if(a1[i]+b1[zhongjian]<0)
60                        tou=zhongjian+1;
61                    else
62                     wei=zhongjian-1;
63             }
64         }
65         cout<<sum<<endl;
66     return 0;
67 }

View Code

4 Values whose Sum is 0 ｐｏｊ２７８５

4 Values whose Sum is 0　ｐｏｊ２７８５