Cod sursa(job #2395131)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 2 aprilie 2019 11:41:46
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

const string file = "nrtri";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647, nmax = 805;

int n, ans, v[nmax];

int main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    sort(v+1, v+n+1);
    for (int i = 1; i < n; ++i){
        int p1 = 0, p2 = 0;
        for (int j = i+1; j <= n; ++j){
            int a = v[i], b = v[i+1];
            while(p1+1 <= n && v[p1+1] <= b-a)
                ++p1;
            while(p2+1 <= n && v[p2+1] < b+a)
                ++p2;
            ans += p2-p1;
            if(i > p1 && i <= p2)
                --ans;
            if(j > p1 && j <= p2)
                --ans;
        }
    }
    fout << ans/3 << "\n";
    return 0;
}