Cod sursa(job #346191)

Utilizator MKLOLDragos Ristache MKLOL Data 7 septembrie 2009 04:28:33
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<stdio.h>
int  N,i1,j1,Sfin,O,v[810],S,x,min=30010,max,aux;
 int caut(int lf,int rh,int mod)
 {
int st=lf,car=0,dr=rh,mid;
while(st<=dr)
{
    mid=(st+dr)/2;
    if(v[mid]<=mod)
    {
        car=mid;
        st=mid+1;
    }
    else if(v[mid]>mod)
    dr=mid-1;

}





    return car;

}
 void qsort(int l,int r)
{
int st=l,dr=r,piv=v[(l+r)/2];
while(st<dr)
{
while(v[st]<piv)
++st;
while(v[dr]>piv)
--dr;
if(st<=dr)
{
aux=v[st];
v[st]=v[dr];
v[dr]=aux;
++st;
--dr;
}
}
if(l<dr)
qsort(l,dr);
if(st<r)
qsort(st,r);


}
int main()
{
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
scanf("%d",&N);
for(int i=1;i<=N;++i)
{
scanf("%d",&x);
v[i]=x;
}
qsort(1,N);

for(int i=1;i<N-1;++i)
    for(int j=i+1;j<N;++j)
    {
    O=caut(1,N,v[i]+v[j]);
    if(j<=O)
    Sfin=Sfin+(O-j);
    }
    printf("%d",Sfin);
}