Cod sursa(job #1581166)

Utilizator Vali_DeaconuVali Deaconu Vali_Deaconu Data 26 ianuarie 2016 17:15:40
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<cstdio>
#include<algorithm>

using namespace std;

#define MAXN 810
typedef int vector[MAXN];

vector v;
int n, triCount;

void file_in() {
    if (freopen("nrtri.in", "rt", stdin));
    if (scanf("%d", &n));
    for (int i=1; i<=n; ++i)
        if (scanf("%d", &v[i]))
            ;
    fclose(stdin);
}

void file_out() {
    if (freopen("nrtri.out", "wt", stdout));
    printf("%d", triCount);
    fclose(stdout);
}

int caut(int st, int dr, int x) {
    int mid, poz, p = st;
    mid = (st+dr)/2;
    while (st <= dr) {
        if (v[mid] <= x) {
            st = mid+1;
            poz = mid;
            mid = (st+dr)/2;
        } else {
            dr = mid-1;
            mid = (st+dr)/2;
        }
    }
    if (p == st)
        return 0;
    return poz-p+1;
}

int main() {
    file_in();

    sort(v+1, v+n+1);

    for (int i=1; i<n-1; ++i)
        for (int j=i+1; j<n; ++j) {
            int x = v[i] + v[j];
            triCount += caut(j+1, n, x);
        }

    file_out();
    return 0;
}