Cod sursa(job #2098280)

Utilizator luanastLuana Strimbeanu luanast Data 2 ianuarie 2018 17:08:31
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("nrtri.in");
ofstream fout ("nrtri.out");
int n,i,j,u,p,mid,v[810],sol,ok1,ok2;
int main(){
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>v[i];
    }
    sort(v+1,v+n+1);
    for(i=1;i<n-1;i++){
        for(j=i+1;j<n;j++){
            p=j+1;
            u=n;
            while(p<=u){
                mid=(p+u)/2;
                if(v[i]+v[j]>=v[mid] && v[i]+v[j]<v[mid+1]){
                    sol+=mid-j;
                    ok1=1;
                    break;
                }
                else
                    if(v[i]+v[j]>=v[mid] && v[i]+v[j]>=v[mid+1])
                        p=mid+1;
                    else
                        if(v[i]+v[j]<v[mid])
                            u=mid-1;
                if(mid==n){
                    ok2=1;
                    sol+=(n-j+1)*(n-j)/2;
                    break;
                }
            }
            if(ok1 || ok2)
                break;
        }
        if(ok2)
            break;
    }
    fout<<sol;
    return 0;
}