Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

SPOJSUMFOUR

Autor: Igor Wolff

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <stack>

using namespace std;

typedef long long int int64;

#define REP(i, n) for (int i = 0; i < n; i++)
#define INF 0x3f3f3f3f
#define EPS 10e-9
#define MAXN 4010
#define ll long long

int A[MAXN],B[MAXN],C[MAXN],D[MAXN];
int v1[MAXN*MAXN],v2[MAXN*MAXN];

int main() {
  int n,n1,n2,t;
  ll ans;
  scanf("%d",&n);
  for (int i=0; i<n; i++)
      scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);

  t = 0;
  for (int i=0; i<n; i++)
    for (int j=0; j<n; j++)
      v1[t++] = A[i]+B[j];

  sort(v1,v1+t);
  n1 = t;

  t = 0;
  for (int i=0; i<n; i++)
    for (int j=0; j<n; j++)
      v2[t++] = -(C[i]+D[j]);

  sort(v2,v2+t);
  n2 = t;

  int i,j;
  i = j = 0;
  ans = 0LL;
  while (i<n1 && j<n2) {
    if (v1[i] < v2[j]) i++;
    else if (v2[j] < v1[i]) j++;
    else {
      int a = 0, b = 0;
      while (i+1 < n1 && v1[i+1] == v1[i]) {
        i++;
        a++;
      }
      while (j+1 < n2 && v2[j+1] == v2[j]) {
        j++;
        b++;
      }
      a++; b++;
      ans += (ll)(a)*(ll)(b);
      i++; j++;
    }
  }

  printf("%lld\n",ans);

  return 0;
}