首页 > 代码库 > uva 1152

uva 1152

中途相遇法

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=4000+10;
int a[maxn][5];
int zz[maxn*maxn];
int n,t;
int main()
{   scanf("%d",&t);
   while(t--)
   {
       scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<4;j++)
            scanf("%d",&a[i][j]);
    }
    int cnt=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        zz[cnt++]=a[i][0]+a[j][1];
        sort(zz,zz+cnt);
        int ans=0;
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {  int hh=-a[i][2]-a[j][3];
            ans+=upper_bound(zz,zz+cnt,hh)-lower_bound(zz,zz+cnt,hh);
        }
    printf("%d\n",ans);
    if(t) printf("\n");
   }
    return 0;
}

 

uva 1152