Cod sursa(job #237799)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 30 decembrie 2008 19:12:55
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<stdio.h>
int n,a[801];
int cautbin(int x,int y){
	int st,dr,m,poz=y;
	st=y+1;
    dr=n;
    while(st<=dr){
        m=(st+dr)/2;
		if(a[m]<=a[x]+a[y]){
            poz=m;
            st=m+1;}
        else
			dr=m-1;}
	return poz;}   
int divide(int p,int q){
    int st,dr,x;
    st=p;
    dr=q;
    x=a[p];
    while(st<dr){
        while(st<dr&&a[dr]>=x)
            --dr;
        a[st]=a[dr];
        while(st<dr&&a[st]<=x)
            ++st;
        a[dr]=a[st];
        a[st]=x;}
    return st;}
void qsort(int p,int q){
    int m;
    m=divide(p,q);
    if(m-1>p)
        qsort(p,m-1);
    if(m+1<q)
        qsort(m+1,q);}
void solve(){
    int i,j,k=0;
    scanf("%d",&n);
    for(i=1; i<=n; ++i)
        scanf("%d",&a[i]);
    qsort(1,n);
    for(i=1; i<n; ++i)
		for(j=i+1; j<n; ++j)
            k+=cautbin(i,j)-j;
    printf("%d",k);}
int main(){
    freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
    solve();
    return 0;}