Cod sursa(job #52432)

Utilizator vmaneavmanea vmanea Data 18 aprilie 2007 21:01:20
Problema Numarare triunghiuri Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <stdio.h>
#include <stdlib.h>
#define infinit 1000000

#define nmax 805

int *p1, *p2, N, i, j, k, tri, ultim, maxmin, maxmax, minim, maxim, left, right, suma;

int dif[nmax][nmax];

int pozmin[60002];

int pozmax[60002];

int L[nmax];

int sortit( const void *a, const void *b)
{
   p1 = (int *)a;

   p2 = (int *)b;

   if (*p1 < *p2)
	return -1;
   if (*p1 == *p2)
	return 0;
   return 1;
}


int main(void)
{
	freopen("nrtri.in", "r", stdin);
	freopen("nrtri.out", "w", stdout);

	scanf("%d", &N);

	for (i = 1; i <= N; ++i)
		scanf("%d", &L[i]);

	qsort((void *)L, N + 1, sizeof(int), sortit);

	for (i = 1; i <= N; ++i)
		for (j = i + 1; j <= N; ++j)
			dif[j][i] = dif[i][j] = L[i] - L[j] > 0? L[i] - L[j]: L[j] - L[i];

	for (i = 0; i <= 60000; i++)
		pozmin[i] = infinit;

	for (i = 1; i <= N; ++i)
	{
		// pozitia minima care incepe cu V[i]

		if (pozmin[L[i]] > i)
			pozmin[L[i]] = i;

		// pozitia maxima care se termina cu V[i]
		if (pozmax[L[i]] < i)
			pozmax[L[i]] = i;
	}

	for (ultim = infinit, i = 60000; i >= 0; i--)
		if (pozmin[i] != infinit)
		{
			ultim = pozmin[i];
			if (ultim > maxmin)
				maxmin = ultim;
		}
		else
			pozmin[i] = ultim;

	for (i = ultim = 0; i <= 60000; ++i)
		if (pozmax[i])
		{
			ultim = pozmax[i];
			if (ultim < maxmax)
				maxmax = ultim;
		}
		else
			pozmax[i] = ultim;

	// de la ce indice spre dreapta am o valoare >= x?

	// de la ce indice spre stangaa am o valoare <= x?

	for (i = 1; i <= N; ++i)
	 for (j = i + 1; j <= N; ++j)
	 {
		minim = dif[i][j];

		maxim = L[i] + L[j];

		left = pozmin[minim] != infinit? pozmin[minim]: maxmin;

		right = pozmax[maxim] != 0? pozmax[maxim]: maxmax;

		if (left <= right)
		{
			suma = right - left + 1;

			if (left <= i && i <= right)
				suma--;

			if (left <= j && j <= right)
				suma--;

			tri += suma;
		}
	 }

	printf("%d\n", tri / 3);

	return 0;
}