Cod sursa(job #40002)

Utilizator thestickTudor A thestick Data 27 martie 2007 10:34:29
Problema Numarare triunghiuri Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
long x[801];
long n;
long nt=0,nt2=0;

int bs(int val)
{
int i, step;
for (step = 1; step < n; step <<= 1);
        for (i = 0; step; step >>= 1)
        if (i + step < n && x[i + step] <= val)
        i+= step;
return i;
}

void cit()
{
long i;
FILE *f=fopen("nrtri.in","r");
fscanf(f,"%d",&n);
for(i=0;i<n;i++)
fscanf(f,"%d",&x[i]);
fclose(f);
}

void rez()
{
long i,j,k;
for(i=n-1;i>1;i--)
for(j=i-1;j>0;j--)
        {
        k=bs(x[i]-x[j]);
        if(k>=j)j=0;
        else nt+=(j-k);
        }
}


void rez2()
{
long i,j,k;
for(i=n-1;i>1;i--)
for(j=i-1;j>0;j--)
for(k=j-1;k>=0;k--)
if(x[k]+x[j]>=x[i])nt2++;
}



void tip()
{
FILE *f;
f=fopen("nrtri.out","w");
//fprintf(f,"%d\n",nt);
fprintf(f,"%d\n",nt2);
fclose(f);
}

int main()
{
cit();
sort(x,x+n);
//rez();
rez2();
tip();
return 0;
}