Cod sursa(job #313846)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 9 mai 2009 21:50:59
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<fstream.h>
int x,m,nr=0,n,k,v[3000+1];
#define Nmax 500005
void part(long st, long dr, long &m){
long p,aux;
long s,d;
p=v[st];
s=st;
d=dr;
while(s<d){
while(s<=dr&&v[s]<=p) s++;
while(d>=st&&v[d]>p) d--;
if(s<d){
aux=v[s];
v[s]=v[d];
v[d]=aux;
}
}
m=d;
aux=v[st];
v[st]=v[m];
v[m]=aux;
}
void quick(long st, long dr){
long m;
if(dr>st){
part(st,dr,m);
if(st<m-1) quick(st,m-1);
if(m+1<dr) quick(m+1,dr);
}
}

int main()
{int i,j;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
f>>n;
for(i=1;i<=n;i++)
    f>>v[i];
quick(1,n);
       for(i=1;i<=n-2;++i)
    {
        k=i+2;
        for(j=i+1;j<=n-1;++j)
        {
            while(k<=n && v[i]+v[j]>=v[k])
                ++k;
            nr+=k-j-1;//k=indicele primului care nu e bun=>toate cele dintre j+1 si k-1 sunt bune
        }
    }
    g<<nr<<'\n';


   return 0;

}