二分 poj2785

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 #include <cstring>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 long long arr[16000010];
10 long long a[4010];
11 long long b[4010];
12 long long c[4010];
13 long long d[4010];
14 
15 int main()
16 {
17     int n;
18     while(scanf("%d",&n)!=EOF)
19     {
20         for(int i=0;i<n;i++)
21         {
22             scanf("%I64d",&a[i]);
23             scanf("%I64d",&b[i]);
24             scanf("%I64d",&c[i]);
25             scanf("%I64d",&d[i]);
26         }
27         for(int i=0;i<n;i++)
28         {
29             for(int t=0;t<n;t++)
30             {
31                 arr[i*n+t]=a[i]+b[t];
32             }
33         }
34         sort(arr,arr+n*n);
35         int num=0;
36         for(int i=0;i<n;i++)
37         {
38             for(int t=0;t<n;t++)
39             {
40                 int tmp=-(c[i]+d[t]);
41                 int s=lower_bound(arr,arr+n*n,tmp)-arr;
42                 while(arr[s]==tmp&&s<n*n)
43                 {
44                     s++;
45                     num++;
46                 }
47             }
48         }
49         cout<<num<<endl;
50     }
51     return 0;
52 }
View Code