Cod sursa(job #807890)

Utilizator ioana.teocIoana Teoc ioana.teoc Data 5 noiembrie 2012 21:18:15
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
//
//  main.cpp
//  Numarare triunghiuri
//
//  Created by Ioana Teoc on 11/5/12.
//  Copyright (c) 2012 Ioana Teoc. All rights reserved.
//

#include <iostream>
#include<stdio.h>

using namespace std;

#define NMAX 800

int V[NMAX], n;

int partition(int l, int r){
    int i = l-1;
    int x = V[r];
    for(int j = l; j < r; j++){
        if(V[j] < x){
            i++;
            swap(V[i], V[j]);
        }
    }
    swap(V[i+1], V[r]);
    return i + 1;
}

void quickSort(int l, int r){
    if(l<r){
        int q = partition(l, r);
        quickSort(l, q-1);
        quickSort(q+1, r);
        
    }
}

int binSearch(int x, int l, int r){
    int step, i, length = r - l + 1;
    
    for(step = 1; step < length; step <<= 1);
    for(i = l - 1; step; step >>= 1){
        if(i + step <= r && V[i + step] <= x)
            i += step;
    }
    return i;
}

int searchTri(){
    int ntri = 0, q;
    for(int i = 0; i < n-2; i++){
        for(int j = i+1; j < n-1; j++){
            q = binSearch(V[i] + V[j], j+1, n-1);
            if(V[i] + V[j] >= V[q])
                ntri += q-j;
        }
    }
    return ntri;
}

int main()
{
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &V[i]);
    }

    quickSort(0, n-1);
    int res = searchTri();
    printf("%d", res);
}