2163.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2163 on 2006-03-09 at 10:51:42 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int LIMIT = 16000000;
const int MAX = 4000;

int num[2][LIMIT], cnt[2][LIMIT];

int enumer(int*, int*, int, int);

int main()
{
	int set[4][MAX], n, i, j;

	while(scanf("%d", &n) != EOF) {
		for(i = 0; i < n; i++)
			for(j = 0; j < 4; j++) scanf("%d", &set[j][i]);
		int total = 0, n1 = enumer(set[0], set[1], n, 0), n2 = enumer(set[2], set[3], n, 1);
		for(i = j = 0; i < n1 && j < n2; )
			if(num[0][i] == num[1][j]) total += cnt[0][i++]*cnt[1][j++];
			else if(num[0][i] < num[1][j]) i++;
			else j++;
		printf("%d\n", total);
	}
	
	return 0;
}

int enumer(int* s1, int* s2, int n, int o)
{
	int i, j, sn = 0, sgn = (o == 0 ? 1 : -1);
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			num[o][sn++] = (s1[i] + s2[j]) * sgn;
	sort(num[o], num[o]+sn);
	int dn = 0;
	for(i = 0; i < sn; i++)
		if(i == 0 || num[o][i] != num[o][i-1]) { cnt[o][dn] = 1; num[o][dn++] = num[o][i]; }
		else cnt[o][dn-1]++;
	return dn;
}