Cod sursa(job #147360)

Utilizator coderninuHasna Robert coderninu Data 2 martie 2008 20:40:53
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <stdio.h>
#define Nmax 801

int n, i, j, v[Nmax], p, q, st, dr, rez;

void sort(int,int);
int searchSt(int,int,int);
int searchDr(int,int,int);
inline int abs(int x) { return x<0?-x:x; }

int main()
{
	freopen("nrtri.in", "r", stdin);
	scanf("%d\n", &n);
	for (i=1; i<=n; i++) scanf("%d ", &v[i]);
	sort(1,n);
	for (i=1; i<n-1; i++)
		for (j=i+1; j<n; j++)
		{
			p=abs(v[i]-v[j]);
			q=v[i]+v[j];
			if (p>v[n] || q<v[j+1]) continue;
			st=searchSt(j+1,n,p);
			dr=searchDr(j+1,n,v[i]+v[j]);
			rez+=dr-st+1;
		}
	fprintf(fopen("nrtri.out", "w"), "%d\n", rez);
	return 0;
}

void sort(int p, int q)
{
	int st=p, dr=q, x=v[st];
	while (st<dr)
	{
		while (st<dr && v[dr]>=x) dr--; v[st]=v[dr];
		while (st<dr && v[st]<=x) st++; v[dr]=v[st];
	}
	v[st]=x;
	if (st+1<q) sort(st+1,q);
	if (st-1>p) sort(p,st-1);
}

int searchSt(int p, int q, int x)
{
	int m=(p+q)>>1;
	if (p==q) return p;
	if (v[m]==x && v[m-1]!=x) return m;
	if (p+1==q)
	{
		if (v[p]>=x) return p;
		else return q;
	}
	if (v[m]<x) return searchSt(m,q,x);
	else return searchSt(p,m,x);
}

int searchDr(int p, int q, int x)
{
	int m=(p+q)>>1;
	if (p==q) return st;
	if (v[m]==x && v[m+1]!=x) return m;
	if (p+1==q)
	{
		if (v[q]<=x) return q;
		else return p;
	}
	if (v[m]<=x) return searchDr(m,q,x);
	else return searchDr(p,m,x);
}