Cod sursa(job #1624522)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 2 martie 2016 11:46:22
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int v[1001];
int main()
{
    FILE *fin=fopen ("nrtri.in","r");
    FILE *fout=fopen ("nrtri.out","w");
    int n,i,j,s,st,dr,mid,tri;
    fscanf (fin,"%d",&n);
    for (i=0;i<n;i++)
        fscanf (fin,"%d",&v[i]);
    sort (v,v+n);
    tri=0;
    for (i=0;i<n;i++)
        for (j=i+1;j<n;j++){
            s=v[i]+v[j];
            //printf ("%d ",s);
            st=j+1;
            dr=n-1;
            while (st<=dr){
                mid=(st+dr)/2;
                if (v[mid]+v[i]>=v[j] && v[mid]+v[j]>=v[i] && v[i]+v[j]>=v[mid])
                    st=mid+1;
                else dr=mid-1;
            }
            //if (v[dr]>v[j])
            //printf ("%d_%d_%d  ",dr,st,tri);
            tri=tri+dr-j;
        }
    fprintf (fout,"%d",tri);
    return 0;
}