Cod sursa(job #2545837)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 13 februarie 2020 16:24:43
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int aib[3000005],v[100005],x,y,n,nr;
int query(int x)
{
    int st=1;
    int dr=n;
    int poz=0;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(v[mij]<=x)
        {
            poz=mij;
            st=mij+1;
        }
        else
            dr=mij-1;
    }
    return poz;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>v[i];
    }
    sort(v+1,v+n+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(v[i]>v[j])
            {
                x=v[i]-v[j];
                y=v[i]+v[j];
            }
            else if(v[i]<v[j])
            {
                x=v[j]-v[i];
                y=v[j]+v[i];
            }
            else
            {
                x=1;
                y=v[j]+v[i];
            }
            nr+=query(y)-query(x-1);
            if(v[i]>=x && v[i]<=y)
                nr--;
            if(v[j]>=x && v[j]<=y)
                nr--;
        }
    }
    g<<nr/3<<'\n';
    return 0;
}