Cod sursa(job #469074)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 6 iulie 2010 09:12:30
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> v;
int n,i,j,x, low, high, mid,s;

int main()
{
	freopen("nrtri.in", "r", stdin);
	freopen("nrtri.out", "w", stdout);
	scanf("%d", &n);
	for(i=1;i<=n;i++)
	{
		scanf("%d", &x);
		v.push_back(x);
	}
	sort(v.begin(), v.end());
	for(i=0;i<n-2;i++)
		for(j=i+1;j<n-1;j++)
		{
			low=j+1;
			high=n-1;
			while(low<high)
			{
				mid=(low+high)/2;
				if(v[mid]<=v[i]+v[j])
					low=mid+1;
				else high=mid;
			}
			if(v[low]>v[i]+v[j])
				low--;
			s+=low-j;
		}
	printf("%d\n", s);
	return 0;
}