题目链接

http://poj.org/problem?id=2785

解题思路

原来学长大致说过思路，两两一组，求和，判断两组是不是能相加和为0；
当时只是停留在思路方面，我就纳闷，两数一组得到两组n*n个数的数，再将两组数的每个数相加判断是否为0的时间复杂度不还是n^4，和不分组的时间复杂度没什么区别。这次看别人题解才知道原来是可以优化的。
由于计算 4 个数的和并不好计算，因此可以使用分治的思想，将 4 组数分为两组，然后每组再分别计算和，最后对两组合进行排序，让正数与负数相加判断是否为 0 即可

AC代码

#include<iostream>
#include<algorithm>
#define ll long long
#define x first
#define y second
const int N=4100;
const int inf=0x3f3f3f3f;
using namespace std;
bool cmp(int a,int b)
{
    return a>b;
}
int n,cnt,p[N*N],q[N*N],a[N],b[N],c[N],d[N],ans;
int main()
{
    cin>>n;
    //一列一组输入
    for(int i=1;i<=n;i++)
    cin>>a[i]>>b[i]>>c[i]>>d[i];
    //分成两组p，q
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    ++cnt,p[cnt]=a[i]+b[j],q[cnt]=c[i]+d[j];
    sort(p+1,p+cnt+1);//从小到大排序
    sort(q+1,q+cnt+1,cmp);//从大到小排序
    int j=1;
    //优化核心
    for(int i=1;i<=cnt;i++)
    {
        while(j<=cnt && p[i]+q[j]>0) j++;
        if(j>cnt) break;
        int k=j;
            //一个p[i]可能对应多个q[j]相加=0
        while(k<=cnt && p[i]+q[k]==0) ans++,k++;
    }
    cout<<ans<<endl;
}