Cod sursa(job #2105884)

Utilizator GarboteialexGarbotei Alex Garboteialex Data 14 ianuarie 2018 15:56:24
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int v[801],n,nrtri,capat1,capat2,inceput1,inceput2,sfarsit1,sfarsit2,r1,r2;

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

int ccapat2(int x, int y, int z){ //cautam cea mai mare pozitie <= capat2
    int lo = y, hi = z, mid, fin = 1;
    while(lo <= hi){
        mid = lo + (hi - lo) / 2;
        if(v[mid] > x){
            hi = mid - 1;
        }else {
            fin = mid;
            lo = mid + 1;
        }
    }
    if(v[fin] <= x){
        return fin;
    }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++){
            capat1 = abs(v[j] - v[i]);
            capat2 = v[j] + v[i];
            inceput1 = max(i,j) + 1;
            inceput2 = max(i,j) + 1;
            sfarsit1 = n;
            sfarsit2 = n;
            r1 = ccapat1(capat1,inceput1,sfarsit1);
            r2 = ccapat2(capat2,inceput2,sfarsit2);
            
            for(int p = r1; p <= r2; p++){
                nrtri ++;
                fout<<v[i]<<" "<<v[j]<<v[p]<<'\n';
            }
            
        }
    }
    fout<<nrtri;
}