Cod sursa(job #1124886)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 26 februarie 2014 14:16:03
Problema Numarare triunghiuri Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
/// Craciun Catalin
///  Nrtri
///   Cautare binara
///    www.infoarena.ro/problema/nrtri
#include <fstream>
#include <iostream>
#include <algorithm>

#define NMax 850
#define sizeMax 800000

using namespace std;

ifstream f("nrtri.in");
ofstream g("nrtri.out");

int n;
int A[NMax];
char intrare[sizeMax], *pointerTo=intrare;
long long tri=0;
int i,j;

inline int atoi()
{
    int x=0;

    for (;!(*pointerTo>='0' && *pointerTo<='9'); ++pointerTo);
    for (; (*pointerTo>='0' && *pointerTo<='9'); ++pointerTo)
        x=x*10+(*pointerTo-'0');

    return x;
}

void parcurgere()
{
    sort(A+1, A+n+1);
    for (i=1;i<=n-2;i++)
        for (j=i+1;j<=n-1;j++)
            for (int k=j+1;k<=n;k++)
                if (A[i]+A[j]>=A[k] && A[j]+A[k]>=A[i] && A[i]+A[k]>=A[j])
                    tri++;
                else
                    break;

    g<<tri<<'\n';
    g.close();
}

void citire()
{
    /// Citire optimizata cu atoi
    f.read(intrare, sizeMax);
    n=atoi();
    for (int i=1;i<=n;i++)
        A[i]=atoi();
}

int main()
{
    citire();
    parcurgere();

    return 0;
}