Cod sursa(job #353987)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 6 octombrie 2009 21:11:45
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<cstdio>
#include<cstdlib>
#define MAXN 800

int n, cnt = 0;
int v[MAXN + 1];

void citeste()
{
	int i;
	FILE* fi = fopen("nrtri.in", "r");
	fscanf(fi, "%d", &n);
	for(i = 0; i < n; ++i) fscanf(fi, "%d", &v[i]);
	fclose(fi);
}

void scrie()
{
	FILE* fo = fopen("nrtri.out", "w");
	fprintf(fo, "%d\n", cnt);
	fclose(fo);
}

int fcmp(const void* a, const void* b)
{
  return ( *(int*)a - *(int*)b );
}

int cautaBinar(int li, int ls, int suma)
{
	int mij;
	if(li == n) return -1;
	while(ls - li > 4)
	{
		mij = (li + ls) / 2;
		if(v[mij] > suma) ls = mij - 1;
		else li = mij;
	}
	int k = -1;
	for(int i = li; i <= ls; ++i)
		if(v[i] <= suma) 
			k = i;
	return k;
}

void rezolva()
{
	int i, j, suma, k;
	
	//sortare
	qsort(v, n, sizeof(int), fcmp);
	
	//fixam doua elemente
	for(i = 0; i < n; ++i)
	{
		for(j = i + 1; j < n; ++j)
		{
			suma = v[i] + v[j];
			
			//il cautam binar pe al treilea
			k = cautaBinar(j + 1, n - 1, suma);
			if(k != -1) cnt += (k - j);
		}
	}
}

int main()
{
	citeste();
	rezolva();
	scrie();
	return 0;
}