Cod sursa(job #1881693)

Utilizator shantih1Alex S Hill shantih1 Data 16 februarie 2017 17:52:06
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include <algorithm>
#include <fstream>

using namespace std;

int n, i, j, v[800], st, dr, nrt, mid, poz, k;

int main () {
    
    ifstream fin("nrtri.in");
    ofstream fout("nrtri.out");
    
    fin >> n;
    for (i = 1; i <= n; i++)    fin >> v[i];
    sort (v+1 , v+n+1);
    
    for (i = 1; i <= n-2; i++)
        for (j = i+2; j <= n; j++)
        {
            k = 1;
            st = i;     dr = j;
            mid = st + (dr-st)/2;
            while (st <= dr)
            {
                if (v[mid]+v[st]>=v[dr] && v[mid]+v[dr]>=v[st] && v[st]+v[dr]>=v[mid])
                {
                    cout << st << " " << mid << " " << dr << "\n";
                    poz = mid;
                    k = 0;
                    if (mid > st+1)     mid--;
                }
                else if (mid < dr-1)    mid++;
                if (mid <= st+1 || mid >= dr-1)
                {
                    if (v[mid]+v[st]>=v[dr] && v[mid]+v[dr]>=v[st] && v[st]+v[dr]>=v[mid])
                    {
                        poz = mid;
                        k = 0;
                    }
                    st = dr+1;
                }
            }
            if (k == 0)     nrt += dr-poz;
        }// 1 2 3 4 5
    
    cout << nrt << "\n";
}