POJ_2785_4 Values whose Sum is 0(lower_bound,upper_bound)

4 Values whose Sum is 0
Time Limit: 15000MS
 
Memory Limit: 228000K
Total Submissions: 16970
 
Accepted: 4954
Case Time Limit: 5000MS
Description
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
28 ) 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

5

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).
제목: 문 제 는 n * 4 의 행렬 을 정 한 다음 에 각 열 에서 하나의 수 를 선택 하여 네 개의 수의 합 이 0 인 조합 이 얼마나 되 는 지 물 어 봅 니 다.
분석: 반절 매 거, 양 방향 검색.제목 데이터 양 이 많 으 니 폭력 은 시간 을 초과 할 것 이다.그래서 우 리 는 다른 방법 을 찾 아야 한다.우 리 는 먼저 AB [k] = A [i] + B [j], CD [k] = C [i] + D [j] 를 미리 처리 한 다음 에 CD 배열 정렬 (sort (CD, CD + k) 을 한 다음 에 AB 배열 의 요 소 를 매 거 진 다음 에 CD 배열 에서 2 분 검색 하면 된다.만약 CD 배열 에 대응 하 는 수가 존재 한다 면, 이 수의 개 수 를 더 하면 어떻게 이 수의 개 수 를 얻 을 수 있 습 니까?여기 서 STL 라 이브 러 리 의 두 가지 함 수 를 교묘 하 게 활용 할 수 있 습 니 다: lowerbound(),upper_bound()。이 두 함수 에 대한 상세 한 설명 은:http://blog.csdn.net/jhgkjhg_ugtdk77/article/details/46229645
제목 링크:http://poj.org/problem?id=2785
코드 목록:

#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<cctype>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
const int maxn = 4000 + 5;

int n;
int A[maxn],B[maxn];
int C[maxn],D[maxn];
int A_B[maxn*maxn],C_D[maxn*maxn];

void input(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);
    }
}

void solve(){
    int index=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){

            A_B[index]=A[i]+B[j];
            C_D[index]=C[i]+D[j];
            index++;
        }
    }

    sort(C_D,C_D+index);
    ll ans=0;
    for(int i=0;i<index;i++){
        int number=-A_B[i];
        ans+=(ll)(upper_bound(C_D,C_D+index,number)-lower_bound(C_D,C_D+index,number));
    }
    printf("%I64d
",ans);
}

int main(){
    input();
    solve();
    return 0;
}