Cod sursa(job #1702223)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 14 mai 2016 19:31:17
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <bits/stdc++.h>
using namespace std;

int v[2005];

int main(void) {
    FILE *fi = fopen("nrtri.in", "r");
    FILE *fo = fopen("nrtri.out", "w");
    int n, ans, st, dr;

    fscanf(fi,"%d",&n);
    for(int i=0; i<n; ++i)
        fscanf(fi,"%d",&v[i]);

    sort(v, v+n);
    ans = 0;

    for(int i=0; i<n-2; ++i) {
        st = i+2;
        dr = i+2;

        for(int j=i+1; j<n-1; ++j) {
            st = max(j+1, st);

            while(st+1<n && v[st]<abs(v[j]-v[i]))
                ++st;
            while(dr+1<n && v[dr+1]<=v[j]+v[i])
                ++dr;
            if(v[st]<abs(v[j]-v[i]) || v[dr]>v[j]+v[i])
                continue;
            ans+=max(dr-st+1,0);
        }
    }

    fprintf(fo,"%d\n",ans);

    fclose(fi);
    fclose(fo);
    return 0;
}