Cod sursa(job #2105899)

Utilizator GarboteialexGarbotei Alex Garboteialex Data 14 ianuarie 2018 16:34:48
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n,v[805],capat1,capat2,inceput,nrtri,r1,r2;

int bincapat1(int x, int y){  //cea mai mica pozitie >= capat1
    int lo = y, hi = n, mid, fina = 0;
    while(lo <= hi){
        mid = (lo + hi) / 2;
        if(v[mid] < x){
            lo = mid + 1;
        }else{
            fina = mid;
            hi = mid - 1;
        }
    }
    if(v[fina] >= capat1 && fina <= n){
        return fina;
    }else{
        return 0;
    }
}

int bincapat2(int x, int y){  //cea mai mare pozitie <= capat2
    int lo = y, hi = n , mid ,fina = 0;
    while(lo <= hi){
        mid = (lo + hi) / 2;
        if(v[mid] > x){
            hi = mid - 1;
        }else{
            fina = mid;
            lo = mid + 1;
        }
    }
    if(v[fina] <= capat2){
        return fina;
    }else{
        return 0;
    }
}

int main(){
    fin>>n;
    for(int i = 1; i <= n; i++){
        fin>>v[i];
    }
    sort(v + 1, v + 1 + n);
    
    for(int i = 1; i < n; i++){
        for(int j = i + 1; j <= n; j++){
            inceput = max(i,j) + 1;
            capat1 = abs(v[j] - v[i]);
            capat2 = v[i] + v[j];
            r1 = bincapat1(capat1, inceput);
            r2 = bincapat2(capat2, inceput);
            for(int p = r1; p <= r2; p++){
                if(v[p] != 0){
                    nrtri++;
                }
            }
        }
    }
    fout<<nrtri;
    return 0;
}