Cod sursa(job #1442603)

Utilizator daniel.grosuDaniel Grosu daniel.grosu Data 25 mai 2015 21:53:26
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#define REP(a,b) for(int a=0; a<(b); ++a)
#define FWD(a,b,c) for(int a=(b); a<(c); ++a)
#define FWDS(a,b,c,d) for(int a=(b); a<(c); a+=d)
#define BCK(a,b,c) for(int a=(b); a>(c); --a)
#define ALL(a) (a).begin(), (a).end()
#define SIZE(a) ((int)(a).size())
#define VAR(x) #x ": " << x << " "
#define FILL(x,y) memset(x,y,sizeof(x))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
#define x first
#define y second
#define st first
#define nd second
#define pb push_back
#define nleft (n<<1)
#define nright (nleft+1)

#include<vector>
#include<algorithm>

using namespace std;
#include<fstream>
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

#define NMAX 805

const int INF = 0x3f3f3f3f;
const int dx[] = {0,0,-1,1}; //1,1,-1,1};
const int dy[] = {-1,1,0,0}; //1,-1,1,-1};

typedef long long LL;
typedef pair<int, int> PII;
typedef long double K;
typedef pair<K, K> PKK;
typedef vector<int> VI;

int n,m,i,j,k,sum;

int s[NMAX];

int upper_binary(int val)
{
    int i,step;
    for(step=1;step<=n;step<<=1);

    for(i=0; step; step>>=1)
        if(i+step<=n && s[i+step] <= val)
            i+=step;
    return i;
}

int lower_binary(int val)
{
    int i, step;
    for(step=1;step<=n;step<<=1);

    for(i=n; step; step>>=1)
        if(i-step>0 && s[i-step] >= val)
            i-=step;
    return i;
}


int main()
{
	fin>>n;
	FWD(i,1,n+1)
		fin>>s[i];
		
	sort(s+1,s+n+1);	
	
	FWD(i,1,n+1)
		FWD(j,i+1,n+1)
		{
			k=upper_binary(s[i]+s[j]);
			if(s[k]<=s[i]+s[j] && k!=j){
				sum+=k-i-1;
				//fout<<i<<" "<<j<<" "<<k<<"\n";
			}
		}
		
	fout<<sum;
	
	return 0;
}