Cod sursa(job #610007)

Utilizator alex_ovidiunituAlex Ovidiu Nitu alex_ovidiunitu Data 24 august 2011 13:41:43
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<iostream>
#include<fstream>
int a[1000];
using namespace std;
int functie(const void *a, const void *b)
{
	return *(int*)a - *(int*)b;
}
int main(void)
{
	int n,i,j;
	fstream f,g;
	f.open("nrtri.in",ios::in);
	g.open("nrtri.out",ios::out);
	f>>n;
	for (i=1;i<=n;i++)
		f>>a[i];
	//sort(a+1,a+n+1);
	int nrsol=0;
	qsort(a+1,n,sizeof(int),functie);
	for (i=1;i<=n;i++)
		for (j=i+1;j<=n-1;j++)
		{
			int st=j+1,dr=n,mij;
			while (st<=dr)
			{
				
				mij=(st+dr)/2;
				if(a[i]+a[j]>=a[mij])
				{ 
					if (a[i]+a[mij]>=a[j])
					{
						if (a[j]+a[mij]>=a[i])
						{
							nrsol++;break;
						}
					}
					else
					{st=mij-1;}
				}
				else
				{st=mij+1;}
			}
		}
	g<<nrsol;
		}