Cod sursa(job #1424537)

Utilizator SwagginInMyJaysaaaaaaaaaaaas SwagginInMyJays Data 24 aprilie 2015 19:45:43
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
#include <fstream>
#include <cstdlib>
#include <utility>
#include <algorithm>
#include <bitset>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <cstring>


#define ll long long
#define llu unsigned long long
#define rep(i, a, b) for (int i = (a) ; i <= (b) ; ++i)

#define mp make_pair
#define pii pair <int, int>
#define SORT(x) sort ((x).begin(), (x).end() )
#define fi first

using namespace std;

static const int NMAX = 800;

int a[NMAX];

inline int Search (int N, int i, int j){
    int st = j + 1 , dr = N - 1 , mid;
    while (st <= dr){
            mid = (st + dr) >> 1;
    if (a[i] + a[j] >= a[mid])
        st = mid + 1;
    else dr = mid - 1;
    }
    return dr;
}


int main(){
    ifstream fin ("nrtri.in");
    ofstream fout ("nrtri.out");
    int N, nr = 0;
    fin >> N;
    for (int i = 0 ; i < N ; ++i)
        fin >> a[i];
    sort(a, a + N );
    for (int i = 0 ; i < N - 1 ; ++i)
        for (int j = i + 1 ; j < N ; ++j)
            nr += (Search(N, i, j) <= j ? 0 : 1);
            fout << nr;
        return 0;
}