Cod sursa(job #472318)

Utilizator robigiirimias robert robigi Data 23 iulie 2010 19:09:53
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
// NumarareTriunghiuri.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"

FILE *f=fopen("nrtri.in", "r");
FILE *g=fopen("nrtri.out", "w");

int n, v[801], nr;


void read()
{
	fscanf(f, "%d", &n);
	for (int i=1; i<=n; i++)
		fscanf(f, "%d", &v[i]);
}



void quicksort(int lo, int hi)
{
	int x=v[(lo+hi)/2];
	int i=lo, j=hi, h;
	do
	{
		while (v[i]<x) i++;
		while (v[j]>x) j--;
		if (i<=j)
		{
			h=v[i]; v[i]=v[j]; v[j]=h;
			i++; j--;
		}
	}while (i<=j);
	if (j>lo) quicksort(lo, j);
	if (i<hi) quicksort(i, hi);
}


void binary(int x, int cv)
{
	int lo=1, hi=n, mid;
	while(hi-lo>0)
	{
		mid=lo+(hi-lo)/2;
		if (v[mid]>x) hi=mid-1;
		else lo=mid+1;
	}
	mid=lo+(hi-lo)/2;
	if (v[mid]<=x)
		nr+=mid-cv+1;
	else
		if (v[mid-1]<=x)
			nr+=mid-cv;
}



void program()
{
	quicksort(1, n);
	for (int i=1; i<n-1; ++i)
		for (int j=i+1; j<n; ++j)
		{
			binary(v[i]+v[j], j+1);
		}
	fprintf(g, "%d", nr);
}



int main()
{
	read();
	program();
	return 0;
}