Cod sursa(job #3133997)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 27 mai 2023 20:44:24
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
//Ilie Dumitru
#include<cstdio>
#include<algorithm>
const int NMAX=805;

int v[NMAX], N;

int main()
{
	FILE* f=fopen("nrtri.in", "r"), *g=fopen("nrtri.out", "w");
	//FILE* f=stdin, *g=stdout;
	int i, j, l, r, mid, p[2], ans=0;

	fscanf(f, "%d", &N);
	for(i=0;i<N;++i)
		fscanf(f, "%d", v+i);
	std::sort(v, v+N);

	for(i=0;i+2<N;++i)
		for(j=i+1;j+1<N;++j)
		{
			l=j;
			r=N;
			while(r-l>1)
			{
				mid=(l+r)>>1;
				if(v[mid]<=v[i]+v[j])
					l=mid;
				else
					r=mid;
			}
			p[0]=l;//v[p[0]]<=v[i]+v[j]
			l=j;
			r=N;
			while(r-l>1)
			{
				mid=(l+r)>>1;
				if(v[mid]<v[j]-v[i])
					l=mid;
				else
					r=mid;
			}
			p[1]=r;//v[p[1]]>=v[j]-v[i]

			if(p[0]>=p[1])
				ans+=p[0]-p[1]+1;
			//printf("%d %d: %d %d\n", v[i], v[j], v[p[0]], v[p[1]]);
		}
	fprintf(g, "%d\n", ans);

	fclose(f);
	fclose(g);
	return 0;
}